Hacker News Reader

Comment by pflanze | Hacker News Reader

Any recommendation for literature on turing machines? The wikipedia article seems to be a bit clouded to me. I know turing machines and CPUs with infinite memory are similar in some ways, and that like lambda calculus they can (somewhat equivalently) be used as a basis to think about computation, but I don't know the details and not having a computer science background will probably be missing some context, but would love to get a proper introduction.

View on HN

Kozen's book that has been mentioned is very good. I also recommend Sipser's "Introduction to the Theory of Computation".

It goes from Deterministic Finite Automata (equivalent in power to regular expressions in their purest sense, as opposed to POSIX regexps) to Context-Free Grammars and then finally Turing Machines. So this will give an idea of the hierarchy that TMs sit in.

Also, there are plenty of variations of Turing Machines with lots of cool properties. If you want to have a look, try searching for "Non-Deterministic Turing Machines", "Probabilistic Turing Machines", or "Alternating Turing Machines".

Second Sipser's "Introduction to the Theory of Computation"

You can think of it as a theoretical machine introduced by Alan Turing which can compute anything that can be computed. If something cannot be computed by Turing machine, then it means that it cannot be computed at all. An important aspect is that it is defined as a simple machine with infinte length tape and a moving head, which can move in any direction. Tape is made up of cells where inputs/outputs are stored. There is also another related proof that says problems are uncountable and programs are countable which means there exist some problems which cannot be solved at all. I would recommend the book Introduction to Automata Theory, Languages, and Computation by Ullman et al. It explains from very simple machine called finite automata to Turing machine. For a beginners introduction Wikipedia entry is still good

The important point is that a TM is capable to calculate everything that is considered to be decidable. It is _the_ computation machine in theoretical CS and different models (eg lambda calculus) are equivalent in computational power. Implementations are a proof-of-concept to show/visualize their power and can be seen as compilers for basic languages.

Their exact mathematical description differs from source to source but the interesting thing is that just a small program (the TM) is capable of calculating everything (efficiency is not the question here).

Depending on your background you may prefer to start with primitive recursive function (and then partial recursive function) or finite-state machine. Some books on computability/decidability theory start with those and introduce Turing machines only after.

Automata and Computability (Kozen)

Reply on news.ycombinator.com