What is a Turing Machine?

A Turing Machine (TM) is a theoretical model of computation devised by Alan Turing in 1936. It defines what can and cannot be computed. Though abstract, it captures the essence of any algorithm.

Components

• Infinite tape — divided into cells, each holding one symbol (or blank). Extends infinitely in both directions.
• Read/write head — reads the symbol in the current cell, writes a new symbol, and moves left or right.
• State register — stores the current state of the machine.
• Transition function (δ) — given the current state and current symbol, specifies: new state to enter, symbol to write, direction to move (L/R/S).

Formal Definition

A Turing Machine is formally defined as a 7-tuple:

(Q, Γ, b, Σ, δ, q₀, F)

Q  = finite set of states
Γ  = tape alphabet (all symbols that can appear on tape)
b  = blank symbol (b ∈ Γ, b ∉ Σ)
Σ  = input alphabet (Σ ⊆ Γ \ {b})
δ  = transition function: Q×Γ → Q×Γ×{L,R,S}
q₀ = start state (q₀ ∈ Q)
F  = set of accepting/halting states (F ⊆ Q)

How a Turing Machine Works

At each step:

1. Read the symbol under the head
2. Look up (current state, current symbol) in the transition function
3. Write the new symbol to the tape
4. Move the head left (L) or right (R), or stay (S)
5. Transition to the new state
6. If new state ∈ F → accept/halt. If no valid transition → reject.

Transition Table Example

Simple TM to replace all 0s with 1s on the tape:

State Transition Diagram

Turing machines can also be represented as state diagrams. Each arrow is labelled: read / write, direction. Accepting states are shown with double circles (same convention as FSMs).

Universal Turing Machine (UTM)

A Universal Turing Machine takes as input a description of any Turing machine M and an input I, and simulates M running on I.

• The UTM reads the description of M from its tape
• This is the theoretical foundation of the stored-program computer — a machine that can run any program encoded as data
• Modern computers are implementations of the UTM concept

Church-Turing Thesis

The Church-Turing Thesis states: "Any function that can be computed by an algorithm can be computed by a Turing machine."

• This is a thesis (philosophical claim), not a mathematical proof — it cannot be proved or disproved
• It defines the limits of what is computable
• Accepted universally — every known algorithm can be implemented as a TM

Turing Completeness

A system is Turing complete if it can simulate any Turing machine. All modern general-purpose programming languages (Python, Java, C++, etc.) are Turing complete — they can compute anything a TM can compute.

What Turing Machines Can and Cannot Do