PHL309 Logic, Language, and Thought
Professor: Craig DeLancey
We'll discuss some features of Kolmogorov Complexity a.k.a.
- 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?
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
I'll post hints while I'm in Tucson!
- "10101010..." forever. (Extra credit, print also just
that is, make a machine that will instead just print "10" fifty times
- "10110111011110111110..." forever.
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?