Машина Тьюринга (Алан Тьюрінг, 1936) — математична модель обчислень, що складається з нескінченної стрічки, поділеної на клітинки, голівки читання/запису, поточного стану та функції переходів δ(стан, символ) → (новий символ, напрямок, новий стан). Незважаючи на простоту, будь-який алгоритм, що взагалі може бути обчислений, може бути обчислений на машині Тьюринга (теза Черча-Тьюринга). Проблема зупинки — чи зупиниться МТ на заданому вхідному слові — нерозв'язна.