Introduction to Computation Theory

Yes, you're correct that I actually don't get as far as the computation. That's coming next - at over 2,000 words it became apparent that the series needed to be segmented.

(I should have called this part 0, or maybe part aleph-0 :))

I won't be blazing new trails here though. My aim is to cover, roughly, the following:

* Turing's attack on the Entschiedungsproblem and the halting problem (if space permits, some context regarding Godel) * The correspondence between Turing Machines and natural numbers, and the corollary that most real numbers are uncomputable. * Rice's theorem, and recursive and recursively enumerable sets. * Possibly some mention of Chaitin's Omega.

All should be covered in an undergraduate course on computability - however I see such misunderstanding of simple ideas like the halting problem that come from a shaky grasp of the unintuitive basics that I wanted to write a genuine introduction.

I'd appreciate any further suggestions for content!