В своей работе Тьюринг описывает изменения в ячейках, производимые так называемым компьютером, или вычислителем (в те времена слово «компьютер» означало человека, а не предмет):
«Вычисление обычно осуществляется путем записи неких символов на бумаге. Представим себе, что эта бумага поделена на клеточки, как тетрадка по арифметике… Поведение компьютера в любой момент времени определяется символами, которые он воспринимает, и его состоянием в данный конкретный момент»[18].
Простейший репертуар символов состоит из 0 и 1, и к этому репертуару прилагается таблица инструкций. Такая таблица может включать в себя, например, следующие правила:
Если головка находится над ячейкой, содержащей 0, то 0 стирается и на его место записывается 1, после чего лента сдвигается вправо.
Если головка находится над ячейкой с символом 1, то 1 стирается и на ее место записывается 1 (снова), после чего лента сдвигается влево.
Если головка находится над ячейкой с символом 0, то 0 стирается и на его место записывается 1, после чего лента сдвигается влево.
Если головка находится над ячейкой с символом 1, то 1 стирается и на ее место записывается 1 (снова), после чего лента сдвигается вправо.
Если головка находится над ячейкой с символом 1, то 1 стирается и на ее место записывается 1 (снова), после чего лента остается на месте.
Эти инструкции (всего лишь часть полной таблицы правил) можно коротко выразить так:
(0,1, П), (1,1, Л), (0,1, Л), (1,1, П) и (1,1, Н)
Таблица инструкций используется снова и снова, пока машина от некоего начального состояния (определенного набора символов) не перейдет к конечному состоянию. При должном применении правил начальное состояние ленты — скажем, двоичное отображение числа 27 — может прийти к конечному состоянию — 729, — нужно только воспользоваться набором инструкций для умножения чисел на самих себя.
Умозрительно изобретя «машину Тьюринга», которая способна решить некую одну задачу с помощью набора инструкций, предназначенного именно для этой задачи, ученый продемонстрировал, что можно изобрести «универсальную машину Тьюринга», способную имитировать все остальные «машины Тьюринга». Набор правил для такой машины эквивалентен программному обеспечению современных компьютеров, которое позволяет использовать их самыми различными способами.
Хотя эта «машина Тьюринга» так и не была создана в действительности, Тьюринг вовсю трудился над производством других, уже вполне реальных устройств для решения задач. Одна из важнейших задач, которую Тьюринг пытался решить и которая остается нерешенной по сей день, — это математическое выражение, названное «гипотезой Римана», оно касается распределения простых чисел среди натуральных.
