PHL309 Logic, Language, and Thought

Professor: Craig DeLancey

Office: CC212A

Email: craig.delancey@oswego.edu

**Current Assignments**
**12 May**
**Review or Turing machines**: we have CC225 from 9:15 to 10:15 on
Monday. We can talk philosophy or build machines or both if you like.

**Test**:
Our final exam 10:30 -- 12:30 in class. Here are some themes:
- Explain the Turing test (what is the test set-up?
What is this strange set-up meant to control for?).
(Some folks -- for shame! -- forgot this very important
concept. Turing calls it the "imitation game," but it
is not called the "Turing Test." We read about it
here.)
- Stating and understanding Godel's First
Incompleteness Theorem;
- Knowing how to give an informal intepretation of the
Godel sentence;
- Understanding Godel numbering;
- Basic understanding of Turing machines;
- the Halting Problem and either reductio showing the
problem cannot be solved (that is, prove the Halting
result using either the diagonal argument or the
impossible machine argument);
- Definition of Kolmogorov Complexity and Chaitin Random;
- interpreting the import of the Halting Problem;
- defining complexity (the definition of descriptive
complexity);
- the incompressibility result;
- Making a simple Turing machine;
- Prove |R| > |N| using Cantor's diagonal argument;

Also: I'm going to try to get us a room where we can have a Turing
Machine workshop from 9:15 -- 10:15. That'll be a time where we
can work together on any machine you want to work on.

**14 May**
We can work on Turing Machines from 1:30 to 2:30 p.m. in room CC232
if you like.

**16 May**
Last day to hand in a Turing Machine.

**Tentative Assignments (subject to revision)**