This is an old revision of the document!
Turing Machines
(Informal reminder.)
Turing machine has
- finite set of control states
- finite tape alphabet
- transition rules: in given state, when reading given symbol on tape, write given symbol and move left or right
The language accepted by Turing machine is the set of inputs starting from which turing machine halts in an accepting state.
On a given input machine can:
- halt and accept
- halt and reject
- infinitely loop
Every well-defined procedure for computing a set of elements can be expressed using Turing machine.
Moreover, translations from related formalisms:
- random-access machines
- recursive functions
- programming languages
There exists an algorithm = There exists a Turing machine
Theorem: There is no algorithm for deciding, given a description of a Turing machine , and an input to the Turing machine, whether will halt on .
Informally: an interpreter (for a sufficiently expressive programming language) cannot determine whether a given program will terminate on a given input.