PHL309 Logic, Language, and Thought

Professor: Craig DeLancey

Office: CC212A

Email: craig.delancey@oswego.edu

Current Assignments27 MarchComplete the handout on Godel Numbering. Read up to chapter 7 inGodel.

In class, we begin discussing Turing.3 AprilI'll be in New Orleans. You can use the classroom to meet and work on Turing machines.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/.And there are others if you google around; let me know if you find a good one. Many won't run on some machines now because browsers are so insidiously rejecting of Java.

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

Tentative Assignments (subject to revision)

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!13 AprilI'll be in Virginia.15 AprilQuest.17 AprilBegin the Halting result. Your own Turing machine homework will be due.20 AprilComplete/review Halting Problem. We'll spend the week reviewing and applying Turing Machines.27 AprilWe'll spend the week on K-complexity.1 MayHomework on K-complexity due.6 MaySecond project due.11 MayFinal exam, in class, 10:30 a.m. -- 12:30 p.m.