Turing machine

A Turing machine is a theoretical model of computation invented by Alan Turing in 1936. It is a foundational concept in theoretical computer science and is used to formalize the idea of an algorithm or mechanical computation.

Definition A Turing machine consists of:

An infinite tape divided into cells, each capable of holding a symbol (usually from a finite alphabet).

A tape head that can read and write symbols and move left or right one cell at a time.

A finite set of states, including a start state and one or more halting (accepting or rejecting) states.

A transition function that, based on the current state and symbol under the head, specifies:

What symbol to write,

Which direction to move (left or right),

Which state to transition to next.

Despite its simplicity, a Turing machine can simulate the logic of any modern computer algorithm and is used to define what problems are computable.

Example Suppose we want to build a Turing machine that decides whether a binary string has an even number of 1s. The machine could:

Start in state q0.

Move through the tape, toggling between states q0 and q1 every time it encounters a 1.

Accept if it halts in q0 (even number of 1s), reject if in q1.

Importance in Mathematics and Computer Science Turing machines are central to:

The Church–Turing thesis, which proposes that anything computable by an algorithm can be computed by a Turing machine.

The study of computability theory, decidability, and complexity classes (like P, NP, etc.).

Contest and olympiad-level problems in computer science and theoretical mathematics.

Relevance to AoPS Students While Turing machines are not commonly seen in middle or high school math competitions, they are relevant for:

Advanced learners exploring computer science theory.

Students preparing for contests like the USACO, Google Code Jam, or university-level CS courses.

Understanding the limits of algorithms and computation.