home

Turing machines

A Turing machine is a finite automaton with access to memory. It’s a mathematical model of computation that describes an abstract machine.

It is assumed with unbounded memory, provided by an infinite tape of discrete cells with each cell containing a character (including an ‘empty’ or blank character).

Formal expression

A Turing machine consists of Q,Σ,Γ,δ,q1,qacc,qrej where Q:finite set of statesΣ:input alphabet ΣΓΓ:the tape alphabet, including the blank symbol δ:transition function in the form Q×Γ(Q×Γ×{L,R})q1,qacc,qrej:start, accept and reject states, where qQ

Transition function

The transition function δ:Q×Γ(Q×Γ×{L,R}) maps one state and one letter from Γ to:

  1. the next state of the automaton
  2. a letter to be written on the current cell of the tape
  3. the direction (Left or Right) the tape head is to move

When annotating this on a state diagram, convention is to mark each edge with readwrite,direction. For example ab,R expresses “if the letter under the tape head is a, then write b and advance the right rightward cell”.

Language

The language of a given Turing machine, M, is expressed as L(M)={wΣ|M accepts w} If wL(M), M reaches an accept state. Otherwise if wL(M) this implies the input resulted in a reject state, or enters an infinite loop.

A language is recognisable is it is accepted by a Turing machine. The machine itself is termed the recogniser of L(M).

Turing machines that do not enter infinite loops are called deciders. A language is decidable always result in an explicit accept or reject state being reached.