PHL309 Logic, Language, and Thought
Professor: Craig DeLancey
Complete the handout on Godel Numbering.
Read up to chapter 7 in Godel.
In class, we begin discussing Turing.
I'll be in New Orleans. You can use the classroom
to meet and work on Turing machines.
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:
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:
and a typical line would look like:
(Which means when in state S0, reading a "1" on
the tape, write a "0" and move right and go into state
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.
- 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
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:
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)
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!
I'll be in Virginia.
Begin the Halting result.
Your own Turing machine homework will be due.
Complete/review Halting Problem.
We'll spend the week reviewing and applying Turing Machines.
We'll spend the week on K-complexity.
Homework on K-complexity due.
Second project due.
Final exam, in class, 10:30 a.m. -- 12:30 p.m.