A class of abstract automata that have the most computational power* known. It can compute anything that can be suitably represented and solved by a step by step procedure (Church-Turing thesis).

_{*computational power refers to how many possible computations, i.e. sets of instructions, it can perform. See Theory of computation}

Math 574, Lesson 2-2: Turing Machines

The main difference between a Turing machine and a Finite-state machine is that a Turing machine has unlimited memory. This is implemented by giving a Turing machine the following components:

• Finitely many states in a read-write head. The states form part of a finite automaton, and may be called the "program".
• An infinite work tape on which the head can read and write. This is the "memory".

Architecture of a Turing machine

Formal definition of a Turing machine

A configuration of the Turing machine consists of the state, the contents of the 2 tapes, and the position of the tape heads.

Example: Math 574, Lesson 2-3: Turing machines - an example that accepts the language composed of strings of the form $0^n1^n$ (see Computability theory).

Halting & output

See here for a definition of the output of a Turing machine (only defined if the machine halts)

Types and variations of Turing machine

• Single-tape
• multi-tape
  • Typical one: One read-only input tape, $k$ working tapes, and one write-only output tape.
• Universal Turing machine
• Turmite