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

Current Assignments
16 April
We'll discuss some features of Kolmogorov Complexity a.k.a. descriptive complexity:
  • A review of Chaitin Random vs. Compressibility vs. Information
  • What yardstick should we use?
  • Do different yardsticks give us different measures?
  • Is this measure decidable?
  • How many strings are Chaitin Random?
21 April
K-complexity and randomness

23, 25 April
While I'm in Tucson, meet in class and work on these problems! 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 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".
I'll post hints while I'm in Tucson!

Tentative Assignments (subject to revision)
28, 30 April: the incompressibility method.
5, 7 May: practical limits to reason.
9 May: what are the implications of these limits to reason?