Mathematics.

computability

Turing Machines

Theory of Computation50 minDifficulty6 out of 10

You should know: finite automata

Overview

A Turing machine is a finite automaton augmented with an infinite tape it can read, write, and move along freely — the simplest model that captures exactly what it means for something to be 'computable.' The Church-Turing thesis holds that anything computable by any reasonable mechanical process (any real computer, any programming language) can be computed by a Turing machine, making it the theoretical foundation of computer science itself.

Intuition

Picture an infinitely long strip of tape divided into cells, and a read/write head that can move left or right one cell at a time, reading the symbol under it and possibly overwriting it, based on a finite rule table and its current internal state. That's the entire machine. Despite this extreme simplicity — no registers, no random access memory, no fancy instructions — it can simulate any modern computer (given enough time and tape), because any computation can be broken down into simple 'read a symbol, write a symbol, move, change state' steps.

Formal Definition

Definition

A (deterministic) Turing machine is a 7-tuple:

M=(Q,Σ,Γ,δ,q0,qaccept,qreject)M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})
Definition
δ:Q×Γ→Q×Γ×{L,R}\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}

Transition function: (state, tape symbol) → (new state, symbol to write, direction to move)

Notation

NotationMeaning
Γ\GammaThe tape alphabet (includes the input alphabet Σ plus a blank symbol)
δ\deltaThe transition function determining the next move
qaccept,qrejectq_{\text{accept}}, q_{\text{reject}}The two special halting states

Theorems

Theorem 1: Church-Turing thesis
Every function that is ’effectively computable’ by any intuitive algorithmic process is computable by some Turing machine.\text{Every function that is 'effectively computable' by any intuitive algorithmic process is computable by some Turing machine.}
Theorem 2: Universal Turing machine
There exists a single Turing machine U that, given the description of any machine M and an input w, simulates M running on w.\text{There exists a single Turing machine U that, given the description of any machine M and an input w, simulates M running on w.}

Applications

The universal Turing machine is the theoretical blueprint for the stored-program computer: a single machine that runs any program given as data.

Worked Examples

  1. Two states tracking parity, moving right across the tape, and accepting/rejecting based on the ending state.

    qeven→read 1, write 1, move Rqoddq_{\text{even}} \xrightarrow{\text{read }1,\text{ write }1,\text{ move R}} q_{\text{odd}}

Answer: A 2-state machine identical in structure to the finite-automaton parity example, but scanning left-to-right on a tape.

Practice Problems

Difficulty 6/10

Why can't a finite automaton (without a tape) simulate a Turing machine in general?

Difficulty 7/10

Why can no program (antivirus, IDE, or compiler) perfectly determine in advance whether ANY given program will eventually halt or run forever?

Difficulty 5/10

The Church–Turing thesis claims that any function 'effectively computable' by any realistic model (your laptop, a supercomputer, a quantum computer for decidability) can be computed by:

Difficulty 6/10

What is a Universal Turing Machine, and which everyday device is its direct conceptual descendant?

Common Mistakes

Common Mistake

Thinking a Turing machine is meant to be a practical computer design.

It's a mathematical abstraction for defining computability, not an engineering blueprint — it's deliberately minimal so proofs about 'what's computable' are as general as possible.

Quiz

The Halting Problem — deciding whether an arbitrary program halts on a given input — is:
A Universal Turing Machine is the conceptual ancestor of:
The Church–Turing thesis essentially says that the Turing machine captures:

Historical Background

Alan Turing introduced the Turing machine in his landmark 1936 paper 'On Computable Numbers,' answering Hilbert's Entscheidungsproblem (decision problem) by proving no algorithm can decide, for every possible input, whether a given program halts. Alonzo Church independently arrived at an equivalent notion (lambda calculus) the same year, and the equivalence of the two models is the Church-Turing thesis.

  1. 1936

    Alan Turing publishes 'On Computable Numbers', introducing the Turing machine

    Alan Turing

  2. 1936

    Alonzo Church independently develops the equivalent lambda calculus

    Alonzo Church

  3. 1950

    Turing proposes the Turing Test for machine intelligence in 'Computing Machinery and Intelligence'

    Alan Turing

Summary

  • A Turing machine is a finite-state automaton plus an infinite read/write tape.
  • The Church-Turing thesis: it captures the full power of 'algorithmic computation'.
  • A universal Turing machine can simulate any other Turing machine given as input — the theoretical ancestor of the stored-program computer.
  • Turing machines are the basis for proving some problems (e.g. the halting problem) are undecidable.

References

  1. WebsiteWikipedia — Turing machine