Машина Тьюринга простыми словами: бумажная лента, изменившая мир

Чтобы понять, на что способны все компьютеры мира, Тьюринг придумал самый примитивный из них.

Машина Тьюринга — это не устройство, а мысленная модель. Она отвечает на вопрос: что значит «вычислить» что-либо вообще, в самом строгом смысле?

Зачем понадобилась воображаемая машина

В 1936 году ещё не было ни одного электронного компьютера, но математики спорили: какие задачи в принципе можно решить механически, по правилам, без вспышек гения? Чтобы ответить, нужно было сначала формализовать само понятие «механического вычисления». Алан Тьюринг сделал это, описав предельно простое устройство.

Из чего она состоит

Всего три части:

• Лента — бесконечная полоса, разбитая на клетки. В каждой клетке записан один символ (например, 0, 1 или пустота). Это и память, и вход, и выход.
• Головка — читает символ под собой и может его перезаписать, а затем сдвинуться на одну клетку влево или вправо.
• Таблица правил — мозг машины. Она говорит: «если ты в состоянии A и видишь символ 1 — запиши 0, сдвинься вправо и перейди в состояние B».

И всё. Никакой математики сверх «прочитал — записал — сдвинулся — сменил состояние». Машина просто механически дёргается по ленте, пока не придёт в состояние «стоп».

Маленький пример

Допустим, мы хотим инвертировать строку из нулей и единиц — поменять каждый 0 на 1 и наоборот. Таблица правил тривиальна:

Головка ползёт вправо, переворачивая биты, и останавливается, дойдя до пустоты. Несмотря на убогость инструментов, так можно запрограммировать сложение, умножение, сортировку — что угодно.

Универсальная машина: предок всех компьютеров

Дальше Тьюринг сделал гениальный ход. Раз таблица правил — это тоже всего лишь набор символов, её можно записать на ленту как данные. Тогда существует универсальная машина Тьюринга: она читает с ленты описание любой другой машины и её вход, а затем имитирует её работу.

Узнаёте? Это ровно идея современного компьютера: программа — это данные в памяти, а процессор — универсальный исполнитель, который умеет проигрывать любую программу. Тьюринг описал архитектуру компьютера за десять лет до того, как такой компьютер построили.

Тезис Чёрча — Тьюринга

Главное следствие звучит почти философски: всё, что вообще может быть вычислено любым мыслимым способом, может вычислить и машина Тьюринга. Ваш ноутбук, суперкомпьютер, квантовый процессор, человек с карандашом — никто из них не способен решить задачу, недоступную этой бумажной ленте. Они быстрее, удобнее, но не «мощнее» по принципиальному охвату задач.

Это и называют тьюринг-полнотой: если язык программирования может имитировать машину Тьюринга, на нём можно написать любой алгоритм. Питон, ассемблер и даже Excel-формулы тьюринг-полны.

Зачем это знать программисту

Машина Тьюринга задаёт верхнюю границу возможного. Из неё следует и проблема остановки (есть задачи, неразрешимые ни одной программой), и понимание, что выбор языка не меняет того, что в принципе вычислимо, — только как удобно это писать. Простая лента из бумаги очертила границы всего цифрового мира, в котором мы живём.