PHL309 Logic, Language, and Thought

Professor: Craig DeLancey

Office: CC212A

Email: craig.delancey@oswego.edu

**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;