PHL309 Logic, Language, and Thought
Professor: Craig DeLancey
Office: CC212A
Email: craig.delancey@oswego.edu



Current Assignments
27 March
Complete the handout on Godel Numbering. Read up to chapter 7 in Godel.

In class, we begin discussing Turing.
3 April
I'll be in New Orleans. You can use the classroom to meet and work on Turing machines.
6 April
Project: 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:
  • 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:
    S0.........1.........0..........R........S1
    (Which means when in state S0, reading a "1" on the tape, write a "0" and move right and go into state S1.)
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):
  1. An addition machine; the machine must be able to handle 0+0, and any other two positive numbers.
  2. A subtraction machine for two number n and m where n >= m (this restriction makes it easier!).
  3. 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.)
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 any two 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/.

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

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.



Tentative Assignments (subject to revision)
8 April
Reading: 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 April
I'll be in Virginia.
15 April
Quest.
17 April
Begin the Halting result. Your own Turing machine homework will be due.
20 April
Complete/review Halting Problem. We'll spend the week reviewing and applying Turing Machines.
27 April
We'll spend the week on K-complexity.
1 May
Homework on K-complexity due.
6 May
Second project due.
11 May
Final exam, in class, 10:30 a.m. -- 12:30 p.m.