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 accepts .
Informally: an interpreter (for a sufficiently expressive programming language) cannot determine whether a given program will terminate and give a positive answer on a given input.
By Theorem and definition of “ accepts ”, there is no algorithm for checking whether there exists a Turing machine computation history that is, a finite sequence of Turing machine configurations from the initial state to an accepting state.