PHL309 Logic, Language, and Thought
Professor: Craig DeLancey
Office: CC212A

Current Assignments
27 April
Read these two popular articles by Gregory Chaitin: this one and this one.
1 May
You can work in teams of 3 or less people for this one and hand in a single homework for the whole team. We're going to approximate Kolmogorov Complexity. We don't have a UTM, so we'll instead count characters on the tape and states. 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. Try to do so with as short a program and as few things on the tape as you can manage; extra credit to the team that has the lowest total count for a problem. If you like, assume that the tape comes completely full of 0s before you add anything to it (that is, each square has on it already a 0, so they don't count unless they are between other characters -- as if you bought the tape pre-zeroed). 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".

Tentative Assignments (subject to revision)
11 May
Final exam, in class, 10:30 a.m. -- 12:30 p.m.
  • Stating and understanding Godel's First Theorem;
  • Stating and understanding Godel's Second Theorem;
  • Knowing how to give an informal intepretation of the Godel sentence;
  • Understanding Godel numbering;
  • Basic understanding of Turing machines;
  • Writing a simple Turing machine;
  • the Halting Problem and either reductio showing the problem cannot be solved;
  • Stating and understanding the Church-Turing thesis;
  • interpreting the import of the Halting Problem;
  • Describing and understanding the Turing test, and the objections (and replies) to AI that Turing considers;
  • Definitions of Kolmogorov Complexity and Chaitin Random;
  • interpreting the effects or import of Kolmogorov Complexity;