PHL309 Logic, Language, and Thought
Professor: Craig DeLancey
Reading: read part 6 of Turing's "Computing
Machinery and Intelligence." A version is available here.
Practice: You can work in teams of 4 or less people for
this one and hand in a single homework for the whole team. We're
going to approximate Kolmogorov Complexity. We will do two
cheats to approximate. First is, for some strings we'll let you
print forever. Second is, we don't have a UTM, so we'll instead
count characters on the tape before the machine starts (including
blanks if you use some specific number of them) and rules in the
rule table. Email or use BlackBoard to send a text file.
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 means you hand in (1) a rule table
and (2) a start tape condition for each string (including that
you can have whatever you want on the tape at the start, but we
count those as cost for your program). Try to do so with as short
a program and/or as few things on the tape as you can manage; extra
credit to the team that has the lowest total count for a problem.
The three strings are:
HINTs: I've been asked if 2 and 3 are impossible. For 2, it can
be done relatively easily. Look at the number behind you, copy
it, add one. Repeat. For 3: consider, what if it were Chaitin
Random? Then you could not compress it. Remember you can both
write rules and put something on the start tape. And all you need
to ensure is that the tape has that string on it when the machine
stops. So what will your start tape look like? If you need more
time, I will accept machines until Friday.
- "10101010..." forever. (Extra credit, print also just
that is, make a machine that will instead just print "10" fifty times
- "10110111011110111110..." forever.
Read The Lucas
Tentative Assignments (subject to revision)
2 and 4 May
First: are we computers? Reviewing Turing's
speculations about artificial intelligence. The
Lucas-Penrose Argument. We might review the Chinese Room
argument. Quantum Computation?
Then, or perhaps at the same time: a bit of review and
summary. Our results on limits, and what they seem to mean
for human reasoning. Review of the impossible machine proof
of the Halting Result, and review of the Incompressibility
Result. Review of your Turing machines!
What have we learned about logic, language, and thought?
Final exam 8:00 - 10:00 am. Sorry! I don't schedule them!
I will post questions sometime soon.