View Single Post
Old 2005-07-07, 20:18   #2
garo's Avatar
Aug 2002
Termonfeckin, IE

2·5·251 Posts

Well you could do worse than picking up Hopcroft and Ullman's Introduction to Automata Theory, Languages and Computation

It has a reasonably good description of Turing machines and the Church-Turing hypothesis. The first edition was a bit technical, CS undergrad level, but I'm told the second is less so.

In the meanwhile here is the short answer.

A Turing machine is an abstract construct for a machine. In the simplest form you have an infinite tape with symbols written on it and a moving read/write head that moves from cell to cell, reading and optionally overwriting a cell's contents. The input alphabet and output alphabet need to be defined for every instance of the machine and so does the set of transitions, (i.e. given the state of the machine and the contents of the cell the head is currently on, what should it do? move left, write, overwrite and if so with what), the start state and set of accepting or final states.

CT says that every computational problem can be translated into such a machine and all known real-world computations have been shown to have a TM equivalent.
garo is offline   Reply With Quote