Машина Тьюринга

О задании 12

В демоверсии ЕГЭ 2026 года появилась новая модель задания 12. Раньше здесь работали с исполнителем Редактор, а теперь нужно выполнить алгоритм для машины Тьюринга — пройти по её таблице переходов шаг за шагом.

Основной способ решения — аккуратная ручная трассировка. Небольшую программу на Python можно написать для проверки, но старый шаблон с методом replace здесь уже не поможет: сначала всё равно придётся понять таблицу переходов.

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

Кто такой Алан Тьюринг

Алан Тьюринг — британский математик и логик, один из основоположников информатики. Его идеи помогли строго определить, что такое алгоритм и какие задачи вообще можно решить с помощью вычислений.

Алан Мэтисон Тьюринг родился 23 июня 1912 года в Лондоне. С детства он интересовался математикой и естественными науками, а позднее учился в Королевском колледже Кембриджского университета.

В 1935 году Тьюринг стал членом научного сообщества Королевского колледжа, а затем защитил докторскую диссертацию в Принстоне. Важно не путать это с Лондонским королевским обществом: его членом Тьюринг стал значительно позже, в 1951 году.

Взлом «Энигмы»

В 1939 году Тьюринг начал работать в Блетчли-парке — британском центре криптоанализа. Вместе с большой командой специалистов он участвовал во взломе сообщений, зашифрованных немецкой машиной «Энигма».

«Энигма» была электромеханической шифровальной машиной. Внешне она напоминала пишущую машинку, но внутри находились роторы, из-за которых одна и та же буква при каждом нажатии могла шифроваться по-разному.

Оператор нажимал клавишу, электрический сигнал проходил через роторы и зажигал лампочку с зашифрованной буквой. После каждого нажатия положение роторов менялось, поэтому простой заменой одной буквы на другую такой шифр не раскрыть.

Настроек было настолько много, что полный перебор вручную не имел смысла. Кроме того, ключи регулярно менялись, поэтому подходящую настройку нужно было находить достаточно быстро.

Для автоматизации поиска использовали электромеханическую машину Bombe. Её создавали, опираясь в том числе на более ранние результаты польских криптоаналитиков; важный вклад в британскую версию внесли Тьюринг, Гордон Уэлчман и их коллеги.

Bombe не расшифровывала сообщение целиком. Она быстро отбрасывала настройки, которые приводили к логическим противоречиям, и оставляла небольшое число вариантов для дальнейшей проверки.

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

Об этом периоде жизни Тьюринга рассказывает фильм «Игра в имитацию» (2014). Смотреть его можно как художественную историю, но не как документальный источник: часть событий и персонажей в фильме изменена.

Другие великие достижения

Компьютер «Колосс»

Рядом с историей Тьюринга часто упоминают компьютер Colossus. Однако его не стоит называть «компьютером Тьюринга»: машину для работы с шифром «Лоренц» проектировала другая команда под руководством Макса Ньюмана, а техническую реализацию возглавлял Томми Флауэрс.

Colossus был одним из первых электронных программируемых цифровых компьютеров. Он использовал тысячи электронных ламп и помогал анализировать сообщения, зашифрованные системой «Лоренц».

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

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

Тест Тьюринга

В 1950 году Тьюринг предложил заменить расплывчатый вопрос «Может ли машина мыслить?» более конкретной проверкой — игрой в имитацию, которую сейчас называют тестом Тьюринга.

Судья общается в текстовом виде с двумя скрытыми собеседниками: человеком и машиной. Его задача — определить, кто из них кто, не опираясь на голос или внешний вид.

Если по ответам судья не может надёжно отличить машину от человека, машина успешно справляется с имитацией. Это не математическое доказательство наличия мышления, а предложенный Тьюрингом способ обсуждать машинный интеллект через наблюдаемое поведение.

Сегодня тест остаётся важной частью истории искусственного интеллекта, хотя способности современных систем оценивают и множеством других способов.

Шифратор речи «Delilah»

Во время войны Тьюринг также участвовал в создании Delilah — экспериментального устройства для шифрования речи.

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

Delilah преобразовывала звуковой сигнал, а принимающее устройство выполняло обратное преобразование. Проект показал работоспособность идеи, но до массового применения не дошёл.

Машина Тьюринга

А теперь перейдём к главному для задания 12 — к машине Тьюринга. Тьюринг описал эту математическую модель в 1936 году, когда пытался строго определить понятие алгоритма. Это не конкретный компьютер, а мысленное устройство с очень простыми правилами.

Проблема разрешимости

В начале XX века математики искали универсальный способ определять, можно ли доказать заданное математическое утверждение в формальной системе. Эта задача получила название проблемы разрешимости.

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

Как устроена машина Тьюринга

Машина Тьюринга — предельно простая модель вычислителя. В ней всего четыре основных элемента:

1. Теоретически неограниченная лента, разделённая на ячейки. В каждой ячейке записан символ конечного алфавита: например, 0, 1 или пустой символ λ.
2. Головка, которая в каждый момент находится над одной ячейкой. За один шаг она может:

• прочитать символ в текущей ячейке;
• записать в неё новый символ;
• сдвинуться на одну ячейку влево или вправо;
• либо завершить работу, если это указано в команде.

3. Состояние — обозначение текущего этапа алгоритма: q0, q1, q2 и так далее. Состояние служит небольшой «памятью» машины.
4. Таблица переходов — сама программа. Строка задаёт текущее состояние, столбец — прочитанный символ, а в ячейке записана команда.

Как читать команду в таблице переходов

Команда обычно состоит из трёх частей: «какой символ записать, куда сдвинуть головку, в какое состояние перейти». Например, команда «0, L, q2» означает: записать 0, сдвинуться влево и перейти в q2. Обозначение L — движение влево, R — вправо. В таблицах этой статьи S означает остановку программы.

Разберём простой пример: машина должна прибавить 1 к двоичному числу. На ленте записано 101₂, то есть 5. После работы должно получиться 110₂, то есть 6.

Шаг 1. Сначала двигаемся вправо до пустой ячейки после числа.

Шаг 2. Возвращаемся на одну ячейку влево — к младшему разряду числа 101.

Шаг 3. Если видим 1, заменяем её на 0 и переносим единицу в следующий разряд, то есть идём ещё левее.

Шаг 4. Повторяем перенос, пока не встретим 0 или пустую ячейку. В нашем случае в следующей же ячейке находится 0. Значит переходим к шагу 5

Шаг 5. Заменяем найденный 0 на 1 и останавливаемся.

Для числа 101₂ (5₁₀) перенос закончится на среднем (втором то есть) разряде, поэтому получится 110₂ (6₁₀).

Теперь свяжем эти действия с состояниями таблицы:

• q0 — движение вправо. На 0 и 1 машина сохраняет символ, сдвигается вправо и остаётся в q0. На пустой ячейке она сдвигается влево и переходит в q1.
• q1 — перенос. На 1 машина записывает 0 и идёт влево. На 0 или пустой ячейке записывает 1 и завершает работу.

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

Пусть на ленте записано 1101. После инверсии получится 0010. Ведущие нули здесь не исчезают с ленты: они остаются обычными символами, хотя при чтении числа их обычно не записывают.

Головка движется слева направо, меняет каждый символ на противоположный и останавливается, когда встречает пустую ячейку.

Составим такую таблицу переходов:

Проследим первые шаги. Начинаем с левой единицы.

По таблице заменяем её на 0 и сдвигаемся вправо.

Следующая ячейка тоже содержит 1: снова записываем 0 и идём вправо.

Затем считываем 0, заменяем его на 1 и продолжаем движение вправо.

И последний раз заменим единицу на ноль и сдвинем читающую головку вправо.

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

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

Важно понимать, что состояния машины работают как своеобразная «память». Даже в этом элементарном примере состояние q₀ «помнит», что мы всё ещё обрабатываем число, и только когда головка встречает пустую ячейку, машина «понимает», что работа закончена, и переходит в состояние остановки.

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

Интересно, что современные процессоры выполняют операцию NOT над 64-битным числом за один такт (доли наносекунды). Машина Тьюринга сделала бы это за 64 шага. Но суть в том, что принципиально обе машины делают одно и то же!

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

Универсальная машина Тьюринга

Но Тьюринг пошёл ещё дальше. Он описал универсальную машину Тьюринга — машину, которая может симулировать работу любой другой машины Тьюринга. Как это работает? На ленту записывается описание другой машины Тьюринга (её таблица переходов) и входные данные для неё. Универсальная машина читает это описание и имитирует работу описанной машины.

Звучит знакомо? Да, ведь это принцип работы современного компьютера! Ваш компьютер — это универсальная машина, которая может запустить любую программу, если её загрузить в память. Программа — это и есть «описание машины Тьюринга», а компьютер — универсальная машина, которая её выполняет.

Проблема остановки

Используя концепцию машины Тьюринга, Тьюринг решил проблему Гильберта, но не так, как тот надеялся. Тьюринг доказал, что универсального алгоритма, решающего проблему разрешимости, не существует.

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

Доказательство использует метод от противного. Предположим, существует программа H, которая может определить, остановится ли любая другая программа. Тогда мы можем написать программу P, которая делает следующее: «Если H говорит, что P остановится, то P зацикливается. Если H говорит, что P зациклится, то P останавливается». Получается логическое противоречие — значит, программа H не может существовать.

Это фундаментальное ограничение вычислений. Есть вопросы, на которые в принципе невозможно ответить алгоритмически, какие бы мощные компьютеры мы ни построили.

Влияние на теорию алгоритмов

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

Используя эту модель, математики смогли доказать неразрешимость множества важных задач. Помимо уже упомянутой проблемы остановки, были доказаны неразрешимыми проблема соответствия Поста, проблема равенства двух контекстно-свободных грамматик и многие другие. Это фундаментальные результаты, показывающие принципиальные границы того, что могут делать компьютеры.

Машина Тьюринга также стала теоретической основой программирования. Все языки программирования, которые вы изучаете — от Python до C++ — можно оценить по критерию «полноты по Тьюрингу». Если язык Тьюринг-полон, это означает, что на нём теоретически можно написать любую вычислимую функцию. Это своего рода знак качества для языка программирования.

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

Наследие Тьюринга

Алан Тьюринг умер в 1954 году в возрасте 41 года, но его идеи стали фундаментом теоретической информатики.

В его честь названа премия Тьюринга — одна из самых престижных наград в области информатики. А придуманная им модель до сих пор помогает объяснять, что такое алгоритм и где проходят границы вычислений.

Для нас машина Тьюринга важна ещё и совсем практично: именно её программу нужно аккуратно выполнить в новом задании 12.

Итоги

В машине Тьюринга есть лента, головка, состояния и таблица переходов. На каждом шаге мы смотрим только на текущее состояние и символ под головкой.

Команду читаем в одном порядке: записать символ → сдвинуть головку → перейти в новое состояние. Если указана остановка S, сначала выполняем запись, а затем завершаем программу.

При ручной трассировке всегда отмечайте три вещи: положение головки, состояние и изменившийся символ. Так вы не потеряете шаг даже в длинном алгоритме.

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