PHL309 Logic, Language, and Thought Professor: Craig DeLancey

Office: Marano 212A

Email: delancey@oswego.edu

Past Assignments28 JanuaryRead the selection from Aristotle. Come to class prepared to explain what Aristotle's view is on the infinite.

2 FebruaryReading. Read the selection from Galileo'sTwo New Sciences: First Day, from pages 11 [49] to 28 [67].

I emailed to you the prefered translation. If you didn't get that email let me know.

Also, a fair translation is freely available here.

4 FebruaryReading. Read from Galileo'sTwo New Sciences: First Day, from pages 28 [67] to 45 [83].

9 FebruaryWe are going to finish our discussion of Galileo's views on infinity. We'll also discuss some other concerns about infinity and infinitesimals that people raised.

To add to our ability to think about these things, we'll also learn a bit of set theory in the next weeks. You can consider reading chapter 19 ofA Concise Introduction to Logic.

13 FebruaryRead sections 19.1 and 19.2 ofA Concise Introduction to Logicto get some background in set theory.16 FebruaryHomework! Working on your own, write up your answers to the following questions, and hand them in at the beginning of class.

- For each claim, identify if it is true or false.
a. {a} ∈ {a, b, c}

b. {a} ∈ {{a}, {b}, {c}}

c. 2 ∈ {1, 2, 3}

d. 2 ∈ {{1}, {2}, {3}}

- For each of these pairs: are they identical? (You can answer "yes" or "no".)
a. {1} and {{1}}

b. {2, 3, 1} and {1, 2, 3}

c. {} and {{}}

d. {7, {a}, 9} and {{a}, 9, 7}

- Give an example of a
propersubset of each of the following sets.a. {a, b, c}

b. {1, 2}

c. {{a}, {b}, {c}}

- For each of the following sets, list all of its subsets. (Remember: if we do not require that the subsets be proper, you can include as a subset the set itself. Remember also our rule, if a set has n things in it, then it has 2
^{n}subsets.)a. {1}

b. {a, b}

c. {{}}

d. {c, d, e}- Assume these sets continue in the simplest way as listed. For problems a and b, can you give an example of a function that relates the first to the second in a 1-to-1 correspondence (an on and onto function that would also be a function if it went backwards)? For problem c, can you find a function that is on and onto, even if it were not 1-to-1? (You can answer these using some basic arithmetic -- no need to get fancy; for example, the function relating the naturals to the even numbers would look like: f(x) = 2x.)
a. {2, 4, 6, 8, 10....} and {200, 400, 600, 800, 1000....}(Note that for c, the second set contains only one element, namely the number one.)

b. {1, 2, 3, 4, 5....} and {1, 3, 5, 7, 9, ....}

c. {1, 2, 3, 4, 5....} and {1}

18 FebruaryFor the next several days we'll be discussing Kant. I'll post our class notes soon.

2 MarchHere are our class overheads for Kant.

Due at the beginning of class: A quick homework. Give an example of a sentence for each of Kant's four kinds: a priori, a posteriori, synthetic, analytic. Each sentence example must be your own (no credit for an example we used in class). Then, can you give an example of an analytic a proiri sentence; an example of a synthetic a posteriori sentence; and a synthetic a priori sentence. (If you disagree with Kant's notions, consider yourself as trying to find examples that he would accept.)

4 MarchStart readingLogicomix, if you got it. It is also on reserve in the library, so you can read it there! It's fun and a quick read, and the glossary is really quite good also. (The glossary is a comic also.) You'll enjoy it, I promise.

11 MarchMidterm. Possible questions include:Remember that for a refresher on set theory, you can read sections 19.1 and 19.2 of

- Reconstruct one of Galileo's arguments that we cannot have an actual infinity or that we cannot have actual infinitesimals. Make your reconstruction an explicit reductio ad absurdum argument, in which you make clear the contradiction, and the premise we reject because of the contradiction.
- Answer some basic questions about set membership, subsets, powersets, the definition of cardinality.
- What is Cantor's Claim (about some proper subsets of infinite sets)? How we can use Cantor's Claim (assuming it works) to answer some of Galileo's arguments?
- Reconstruct Cantor's Diagonal Argument to prove that the cardinality of the reals is greater than the cardinality of the natural numbers.
- What is Cantor's Theorem?
- How does Cantor's Theorem, and the claim that a set exists if we can determine its members, result in Cantor's Antinomy.
- Give an example of a sentence for each of Kant's four kinds: a priori, a posteriori, synthetic, analytic. Give an example of a sentence for each of Kant's complex kinds: analytic a priori, synthetic a priori, synthetic a posteriori.
A Concise Introduction to Logic.13 MarchReview of test. Then: Hilbert's questions. Completeness, soundness, consistency, decidability.

Read chapters 1 and 2 of Casti'sGodelif you purchased it.27 MarchComplete the handout on Godel Numbering. Read up to chapter 7 inGodel.

In class, we begin discussing Turing.6 AprilProject: make two (or maybe 3) Turing machines. You may work in teams of 3 or fewer people. You are going to make two or three Turing machines (none universal!). You will do this by giving me, for each machine:It is most elegant to make your machine have an alphabet of 1 and 0, but that's not required. You will hand in at least two machines clearly explained that do the following two problems (or three machines, if you attempt the extra credit):

- Your alphabet
- An explanation of how the tape will be interpreted; this includes where the tape head will start, and where it will end (e.g., something like: "two numbers will be represented by quantity of '1s', separated by a single '0', the tape head will start on the leftmost figure of the left number, and end on the leftmost figure of the final output number").
- Your rule table. It will have a header like:

STATE.....INPUT.....OUTPUT.....MOVE.....STATE

and a typical line would look like:

S_{0}.........1.........0..........R........S_{1}

(Which means when in state S_{0}, reading a "1" on the tape, write a "0" and move right and go into state S_{1}.)Be sure the machine will work for any numbers that meet the requirement. That is, don't make a machine that can add only 2 and 2 for the first problem -- your machine must be able to add

- An addition machine; the machine must be able to handle 0+0, and any other two positive numbers.
- A subtraction machine for two number n and m where n >= m (this restriction makes it easier!).
- Extra credit! A multiplication that multiplies two numbers n*m. (This one is much easier if you allow yourself a bigger alphabet than just 1 and 0; but I'll be very impressed if you can do it with 1 and 0.)
anytwo natural numbers.

One way you can test your ideas and get ideas is to play with some of the turing machine simulators that some scholars have written. Here are some:http://math.hws.edu/TMCM/java/xTuringMachine/.I'm sorry that those resist running on most machines. Security requirements are growing prohibitive and prevent many programs from running.

http://www.turing.org.uk/turing/scrapbook/tmjava.html .

Here is a video of a Turing machine made out of legos!

Here is a fun video of a machine made to look like Turing's imagined machine.8 AprilReading:read the first 5 parts of Turing's "Computing Machinery and Intelligence." A version is available here. What does Turing mean by "the imitation game"? Be able to describe it. I might give you a quiz on it!10 AprilReading:read the remaining parts of Turing's "Computing Machinery and Intelligence." A version is available here.13 AprilI'll be in Virginia. I recommend that you meet together in class, and work together on Turing machines. If you did not write a multiplication machine before, attempt to do so now, and I will still give you extra credit for the machine if yours works.15 AprilQuest.17 AprilWe will introduce the Halting Problem.

I tried to post a homework for when I was away, but FTP failed me and it did not appear here. I'll make it due on Monday then.20 AprilSolo Turing machine project due.

Make a Turing machine that can tell whether a number is evenly divisible by 3. Specify the tape interpretation, where to start the machine, and how to interpret its answer and where the answer will be. Provide also of course the rule table. Best if the rule table is of the form: In-State, Reading, Write, Move, Go-To-State. Do this homework on your own. You need not handle zero.

The rest of the week will be dedicated to the Halting Problem.22 AprilBefore class, play with a Conway Life world. Here's one.27 AprilRead these two popular articles by Gregory Chaitin: this one and this one.1 MayYou can work in teams of 3 or less people for this one and hand in a single homework for the whole team. We're going toapproximateKolmogorov Complexity. We don't have a UTM, so we'll instead count characters on the tape at the beginning, and states and rules in the machine. Using for each as small an alphabet as you can manage, make three turing machines and start tapes that can "print" (that is, will leave the tape such that on it there is) the following three strings. Of course, that meansyou hand in (1) a rule table and (2) a start tape condition for each string (including the contents of the tape at the start of the program--that is, you can put whatever you want on the tape at the beginning). Try to do so with as short a program and as few things on the tape as you can manage; extra credit to the team that has the lowest total count for a problem. If you like, assume that the tape comes completely full of 0s before you add anything to it (that is, each square has on it already a 0, so they don't count unless they are between other characters -- as if you bought the tape pre-zeroed). The three strings are:The important thing is that the string gets on the tape, so remember that's what matters. The first one is easy; the second one a bit harder (try putting a number on the tape, and writing a program that copies a number and adds one, then starts over). The last one is suspicious, don't you think? What does the concept of Chaitin Randomness tell us we should expect?

- "10101010..." forever. (Extra credit, print also just "1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010", that is, make a machine that will instead just print "10" fifty times only.)
- "10110111011110111110..." forever.
- "10010101010010111110010000001110110110010010010110100101001000011001001001011101001001010110100100010".