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 $M$, and an input $w$ to the Turing machine, whether $M$ accepts $w$.

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 “$M$ accepts $w$”, 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.