We’ve had a very rudimentary chapter on Turing machines in the OLP for a while. Samara and I have been working on expanding this over the last few months, using Nicole’s notes and writing some stuff from scratch. It is now is mature enough, I think, that it can be included. So I have merged the
turing-machines branch into
A decisions of which variant of Turing machines to use had to be made. We opted for a version that allows the machine to write and move at the same time, since most of the online emulators work that way. We also decided to let the tape be infinite in one direction only. This makes the proof of undecidability of logic, which requires describing Turing machine configurations, a lot simpler.
It still needs work, of course, like everything else. More examples, more problems, a more in-depth discussion of the Church-Turing thesis, proofs of equivalence of different Turing machine variants, for instance. To tie it to the other computability material, I’d like to show that recursive functions are Turing computable. It would also be great to have some discussion of computational complexity and non-deterministic computation; Dean indicated that he might work in that direction.