Как машина из простых шагов выполняет разные алгоритмы
Машину Тьюринга удобно представить как условное устройство с лентой, разделённой на ячейки, головкой для чтения и записи и набором правил. В каждом шаге головка смотрит на символ, записывает новый или оставляет прежний, сдвигается влево или вправо и меняет своё внутреннее состояние. Состояние — это часть «памяти» машины: оно помогает определить, какое правило применить дальше.
Сама схема машины проста, но правила можно составить по-разному. Один набор заставит её складывать числа, другой — проверять строку или преобразовывать последовательность символов. Алгоритм здесь — точное описание таких действий, которое не требует от исполнителя догадок.
Что означает «универсальная»
Универсальная машина Тьюринга не хранит отдельное устройство для каждой задачи. Вместо этого на ленту можно поместить описание другой машины — то есть её правила, — и данные, с которыми та должна работать. Универсальная машина читает это описание и шаг за шагом имитирует работу заданного алгоритма.
Так один и тот же механизм способен выполнять множество разных программ: меняется не устройство, а записанная на ленте инструкция. Именно эту идею позже воплотили современные компьютеры, где программа и обрабатываемые данные представлены в памяти.
Почему универсальность не означает всеведение
Важное условие — задача должна быть вычислимой: для неё должен существовать алгоритм, который выдаёт ответ за конечное число шагов. Если подходящего алгоритма нет, бесконечная лента и сколь угодно долгое ожидание не помогут.
Например, не существует общего алгоритма, который для любой программы заранее определит, завершится ли она на заданных входных данных или будет работать бесконечно. Машина Тьюринга показывает и силу вычислений, и их границу: любые вычислимые задачи можно свести к исполнению правил, но не всякий вопрос можно превратить в такой алгоритм.
