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



Current Assignments
27 April
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:
  • "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".
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.

29 April
Read The Lucas Argument.




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!
6 May
What have we learned about logic, language, and thought?
11 May
Final exam 8:00 - 10:00 am. Sorry! I don't schedule them! I will post questions sometime soon.