---
tag: 758EYCN27B
kind: concept
name: Turing machine
msc: [03D10, 68Q04]
sources:
  - url: https://en.wikipedia.org/wiki/Turing_machine
same_as:
  wikidata: Q163310
  wikipedia: Turing machine
---

## Summary

A Turing machine is an abstract model of computation with a finite set of states and an unbounded tape of symbols.
A moving head reads and writes the symbols one cell at a time.
Alan Turing introduced it in 1936 to make the notion of an algorithm precise.
A function is computable when some Turing machine computes it, and by the [[Church–Turing thesis|RWRNBS3Z7B]] this matches the informal idea of an algorithm.
Turing machines are the standard model in [[computability theory|X14Y880PN5]] and in complexity theory.

## Explanations

### L1 human

Picture a long strip of paper divided into cells, each holding one symbol, and a reading head that sees one cell at a time.
The machine is in one of finitely many states, like moods.
At each step it reads the symbol under the head, writes a symbol, moves one cell left or right, and changes state, all by a fixed table of rules.
For example, a machine can scan a word of $0$s and $1$s from left to right and flip each digit, stopping at the first blank cell.
Despite this simplicity, every algorithm can be carried out by such a machine.