О задании 12
В 2025/2026 учебном году формулировка задания 12 ЕГЭ по информатике претерпела значительные изменения. Ранее в 12 заданиях требовалось определить результаты работы исполнителя Редактор: выполнить несложный алгоритм по замене символов в строке и вывести результат на экран.
Теперь же, хоть суть задания и осталась та же — работа с заменой символов в строке — но алгоритм решения изменился до неузнаваемости. Если в прошлых версиях этого задания нам достаточно было составить шаблонную программу на языке Python, то теперь это задание решается исключительно ручным методом.
Для успешного решения 12 задания нам необходимо «симулировать» работу такого устройства как машина Тьюринга. Так что давайте в этой статье ближе познакомимся как с работой этой машины, так и с её создателем — знаменитым британским математиком и логиком — Аланом Тьюрингом.
Кто такой Алан Тьюринг
Представьте себе человека, который едет на работу на велосипеде… в противогазе. Не потому, что воздух плохой или чем-либо заражён, а потому что у этого человека аллергия на пыльцу, и он нашёл такое нестандартное решение проблемы. Это и был Алан Тьюринг — один из самых блестящих умов XX века, человек, который заложил основы современной информатики.
Алан Мэтисон Тьюринг родился 23 июня 1912 года в Лондоне. С детства он отличался необычайной любознательностью и математическими способностями. В школе он мог часами решать сложнейшие задачи, но при этом получал замечания за плохой почерк и неаккуратность — типичная история многих гениев.
У Тьюринга была ещё одна странная привычка: он приковывал свою кружку цепью к батарее, чтобы коллеги её не забирали. А во время Второй мировой войны, опасаясь инфляции, он закопал серебряные слитки где-то в лесу, составил карту… и потом не смог её расшифровать. Слитки, кстати, он так и не нашёл.
Но за всеми этими чудачествами скрывался ум невероятной силы. Тьюринг изучал математику в Кембриджском университете, где уже в 22 года стал членом Королевского общества. Затем он отправился в Принстон, где защитил докторскую диссертацию. Казалось бы, обычная карьера учёного, но началась Вторая мировая война, и судьба Тьюринга кардинально поменялась.
Взлом «Энигмы»
В 1939 году Тьюринга пригласили работать в Блетчли-Парк — секретный центр британской криптографии. Перед ним и его коллегами стояла задача, которую многие считали невыполнимой: взломать немецкую шифровальную машину «Энигма».
Что же такое «Энигма»? Это была электромеханическая машина размером с пишущую машинку, которая шифровала сообщения настолько сложным способом, что немцы считали её, как и многие свои «творения» — вершиной инженерной мысли, взломать которую не сможет никто.
Эта машина имела клавиатуру, несколько вращающихся роторов и панель с лампочками. Когда оператор нажимал букву на клавиатуре, электрический сигнал проходил через роторы (каждый из которых можно было установить в одну из 26 позиций), отражался от рефлектора и возвращался обратно, зажигая лампочку с зашифрованной буквой.
Количество возможных комбинаций настроек «Энигмы» превышало 150 триллионов! Каждый день в полночь немцы меняли настройки, поэтому взломать код нужно было заново каждые 24 часа. Представьте себе: даже если бы вы проверяли миллион комбинаций в секунду, вам понадобились бы годы, чтобы перебрать их все.
Тьюринг не стал перебирать все варианты. Вместо этого он создал электромеханическое устройство под названием «Бомба» — «Turing Bombe» (название было заимствовано у польских криптографов, которые начали работу над «Энигмой» ещё до войны).
«Бомба» использовала логические рассуждения и известные слабости немецких процедур шифрования, чтобы значительно сузить круг возможных настроек. Машина могла проверять тысячи вариантов одновременно, автоматизируя процесс взлома.
Благодаря работе Тьюринга и его команды союзники могли читать немецкие военные сообщения. Историки считают, что это сократило войну как минимум на два года и спасло миллионы жизней. Однако после войны вся эта деятельность была засекречена на десятилетия, и Тьюринг не получил заслуженного признания при жизни.
Эта история легла в основу фильма «Игра в имитацию» (2014), где роль Тьюринга исполнил Бенедикт Камбербэтч. Фильм, хоть и содержит некоторые художественные преувеличения, хорошо передаёт напряжённость той работы и гениальность подхода Тьюринга к решению, казалось бы, нерешаемых задач.
Другие великие достижения
Компьютер «Колосс»
Работа над «Бомбой» заставила Тьюринга и его коллег задуматься о создании более быстрых, полностью электронных вычислительных устройств. Кульминацией этих идей стало создание компьютера «Колосс» (Colossus).
Это был один из первых в мире электронных программируемых цифровых компьютеров. Его использовали для взлома ещё более сложного немецкого шифра «Лоренц» (шифр Гитлера). «Колосс» использовал тысячи электронных ламп и был настоящим чудом техники.
Он не был «машиной Тьюринга» в чистом виде (это был не универсальный, а специализированный компьютер), но его архитектура и электронный принцип работы стали основой для всего, что появилось позже.
Тест Тьюринга
После войны Тьюринг задался философским вопросом: «Может ли машина мыслить?» В 1950 году он предложил знаменитый тест, названный его именем.
Суть теста проста: в нем участвуют три субъекта: человек-судья, человек-собеседник и машина (компьютерная программа). Все трое находятся в разных комнатах, и их общение происходит исключительно в текстовом формате. Это ключевое условие, поскольку оно устраняет любые внешние факторы, такие как тембр голоса или внешний вид, которые могли бы выдать машину. Задача судьи — определить, кто из двух анонимных собеседников является человеком, а кто — машиной.
Машина считается прошедшей Тест Тьюринга, если после продолжительного общения судья не может с уверенностью отличить ее ответы от ответов человека. То есть, машина успешно имитирует человеческое разумное поведение. Тьюринг считал, что если машина может убедить человека в своей «человечности» через диалог, то нет смысла говорить, что она «не думает».
Тест Тьюринга до сих пор остается важной вехой и вызовом для разработчиков ИИ, хотя современные исследования часто фокусируются на более специфических задачах.
Шифратор речи «Delilah»
Если «Энигма» и «Колосс» были связаны со взломом чужих кодов, то после войны Тьюринг сосредоточился на создании собственных, надежных систем шифрования. В 1944–1945 годах, работая в Хэнслоп-Парке, он возглавил проект по разработке шифратора речи «Delilah».
Целью проекта было создание устройства для защищенной голосовой связи по телефонным линиям, прежде всего для высшего командования (например, для разговоров между премьер-министром Черчиллем и президентом США). Существующие линии были крайне уязвимы для прослушивания, и требовалось решение, которое делало бы перехваченную речь совершенно непонятной.
Принцип работы «Delilah» основывался на аналоговом шифровании. Он брал человеческую речь и электронным способом «перемешивал» ее: делил голос на частотные полосы, менял их местами и инвертировал частоты. В результате на линии передавался невнятный шум. Для восстановления исходного голоса на принимающей стороне требовалось идентичное устройство «Delilah» с теми же настройками шифрования.
Тьюринг лично демонстрировал работу устройства, зашифровав и расшифровав записанное сообщение. «Delilah» была технически успешна и, используя относительно небольшое количество электронных ламп, обеспечивала высокий уровень безопасности, который превзошли только спустя десятилетия.
Однако, поскольку разработка была закончена лишь к концу войны, а сама машина была сложной и дорогой в производстве, она так и не пошла в массовое использование. Тем не менее, это был один из первых шагов к современным технологиям цифрового кодирования голоса.
Машина Тьюринга
А теперь перейдём к главному — к машине Тьюринга. Парадоксально, но это устройство, оказавшее колоссальное влияние на развитие информатики, было придумано Тьюрингом в 1936 году, когда ему было всего 24 года, и существовало только на бумаге. Более того, Тьюринг создал её не для практического использования, а для решения абстрактной математической проблемы.
Проблема разрешимости
В начале XX века математики пытались формализовать само понятие «алгоритм». Великий немецкий математик Давид Гильберт поставил вопрос: «существует ли универсальный алгоритм, который мог бы определить, имеет ли любое математическое утверждение доказательство?» Это называлось проблемой разрешимости.
Чтобы ответить на этот вопрос, нужно было сначала строго определить, что такое «алгоритм» вообще. И вот здесь на сцену выходит машина Тьюринга.
Как устроена машина Тьюринга
Машина Тьюринга — это абстрактная модель вычислительного устройства, максимально упрощённая, но при этом способная выполнить любые вычисления, которые можно алгоритмизировать. Представьте себе:
- Бесконечная лента, разделённая на ячейки. В каждой ячейке может быть записан символ из конечного алфавита (например, 0, 1 или пустой символ).
- Головка, которая находится над одной из ячеек ленты. Она может:
- Прочитать символ в текущей ячейке
- Записать новый символ в эту ячейку
- Сдвинуться на одну ячейку влево или вправо
- Остаться на месте
- Внутренние состояния— конечный набор состояний, в которых может находиться машина (например, q₀, q₁, q₂… и специальное состояние «стоп»).
- Программа (таблица переходов)— набор правил вида: «Если машина находится в состоянии q₁ и читает символ 0, то запиши 1, перейди в состояние q₂ и сдвинь головку вправо».
Давайте рассмотрим простейшую машину Тьюринга, которая добавляет 1 к двоичному числу.
Допустим, на ленте записано число 101 (это 5 в двоичной системе). Наша задача — получить 110 (6 в двоичной системе).
Составим такой алгоритм:
Двигаемся вправо до конца числа (до пустой ячейки)
Возвращаемся на одну ячейку влево (к последней цифре).
Если видим 1, меняем на 0 и идём ещё левее (это «перенос» разряда).
Повторяем, пока не встретим 0 или пустую ячейку (в нашем случае — 0).
Меняем 0 на 1 и останавливаемся.
Таблица переходов (точнее словесное её описание) может выглядеть так:
- Состояние q₀ (движемся вправо): если 0 или 1 — пишем то же самое, сдвиг вправо, остаёмся в q₀; если пусто — сдвиг влево, переход в q₁. Здесь мы просто сдвигаемся с начала ленты в конец нашего числа.
- Состояние q₁ (изменяем цифры): если 1 — пишем 0, сдвигаемся влево, остаёмся в q₁; если 0 или пустая ячейка — пишем 1 и завершаем работу.
Давайте рассмотрим еще один пример работы машины Тьюринга: пусть она будет инвертировать двоичное число (заменять все единицы на нули и нули на единицы).
Пусть у нас на ленте записано число 1101, в результате работы нашего алгоритма должно получиться 0010.
Наша машина теперь будет двигаться слева направо, начиная с единицы, меняя каждый символ на противоположный, пока не дойдет до конца числа (пустой ячейки).
Составим такую таблицу переходов:
Теперь давайте пошагово проследим за работой алгоритма. Итак, начинаем с единицы.
По таблице меняем её на 0 и сдвигаемся вправо.
Снова читающая головка указывает на единицу, проделываем аналогичные действия: заменяем на 0 и сдвигаемся вправо.
Теперь считывается 0, значит, меняем его на 1 и сдвигаем головку вправо.
И последний раз заменим единицу на ноль и сдвинем читающую головку вправо.
Почему последний? Потому, что мы «упёрлись» в конец числа — пустую ячейку. И, согласно таблице переходов, на этом программа должна завершиться — перейти в состояние «стоп».
Этот простой пример демонстрирует несколько важных принципов работы машины Тьюринга. Во-первых, машина обрабатывает данные строго последовательно, ячейка за ячейкой — она не может «увидеть» всё число сразу, в отличие от человека. Во-вторых, мы видим, как локальные правила приводят к глобальному результату: каждое отдельное правило предельно простое («если видишь 0, пиши 1»), но их комбинация даёт осмысленный результат для всей строки данных.
Важно понимать, что состояния машины работают как своеобразная «память». Даже в этом элементарном примере состояние q₀ «помнит», что мы всё ещё обрабатываем число, и только когда головка встречает пустую ячейку, машина «понимает», что работа закончена, и переходит в состояние остановки.
Наконец, машина Тьюринга полностью детерминирована: на каждом шаге она точно знает, что делать, следуя своей таблице переходов. Нет никакой случайности или неопределённости — один и тот же вход всегда даст один и тот же результат. Именно эта предсказуемость и делает машину Тьюринга идеальной математической моделью для изучения алгоритмов и вычислений.
Интересно, что современные процессоры выполняют операцию NOT над 64-битным числом за один такт (доли наносекунды). Машина Тьюринга сделала бы это за 64 шага. Но суть в том, что принципиально обе машины делают одно и то же!
Процессор просто оптимизирован для параллельной обработки всех битов одновременно, а машина Тьюринга — это теоретическая модель, которая показывает, что вычисление вообще возможно. Она доказывает, что любую операцию можно разложить на последовательность элементарных шагов, и именно это делает её фундаментом всей теории алгоритмов.
Универсальная машина Тьюринга
Но Тьюринг пошёл ещё дальше. Он описал универсальную машину Тьюринга — машину, которая может симулировать работу любой другой машины Тьюринга. Как это работает? На ленту записывается описание другой машины Тьюринга (её таблица переходов) и входные данные для неё. Универсальная машина читает это описание и имитирует работу описанной машины.
Звучит знакомо? Да, ведь это принцип работы современного компьютера! Ваш компьютер — это универсальная машина, которая может запустить любую программу, если её загрузить в память. Программа — это и есть «описание машины Тьюринга», а компьютер — универсальная машина, которая её выполняет.
Проблема остановки
Используя концепцию машины Тьюринга, Тьюринг решил проблему Гильберта, но не так, как тот надеялся. Тьюринг доказал, что универсального алгоритма, решающего проблему разрешимости, не существует.
Более того, он доказал, что невозможно создать алгоритм, который для любой программы и любых входных данных определит, остановится ли программа или будет работать вечно. Это называется проблемой остановки.
Доказательство использует метод от противного. Предположим, существует программа H, которая может определить, остановится ли любая другая программа. Тогда мы можем написать программу P, которая делает следующее: «Если H говорит, что P остановится, то P зацикливается. Если H говорит, что P зациклится, то P останавливается». Получается логическое противоречие — значит, программа H не может существовать.
Это фундаментальное ограничение вычислений. Есть вопросы, на которые в принципе невозможно ответить алгоритмически, какие бы мощные компьютеры мы ни построили.
Влияние на теорию алгоритмов
Машина Тьюринга стала краеугольным камнем теоретической информатики и оказала огромное влияние на развитие этой науки. Прежде всего, она позволила строго классифицировать задачи по сложности. Теперь мы можем точно определить, какие задачи являются «простыми» — то есть решаются за полиномиальное время, а какие «сложными» — требующими экспоненциального времени. Знаменитые классы сложности P и NP, о которых вы могли слышать в контексте нерешённых математических проблем, определяются именно через машину Тьюринга.
Используя эту модель, математики смогли доказать неразрешимость множества важных задач. Помимо уже упомянутой проблемы остановки, были доказаны неразрешимыми проблема соответствия Поста, проблема равенства двух контекстно-свободных грамматик и многие другие. Это фундаментальные результаты, показывающие принципиальные границы того, что могут делать компьютеры.
Машина Тьюринга также стала теоретической основой программирования. Все языки программирования, которые вы изучаете — от Python до C++ — можно оценить по критерию «полноты по Тьюрингу». Если язык Тьюринг-полон, это означает, что на нём теоретически можно написать любую вычислимую функцию. Это своего рода знак качества для языка программирования.
Наконец, и это, пожалуй, самое важное — машина Тьюринга помогла понять фундаментальные границы вычислимости. Она показала, что существует чёткая граница между тем, что можно вычислить (пусть даже за очень долгое время), и тем, что вычислить невозможно в принципе, какие бы мощные компьютеры мы ни создали. Это глубокое философское прозрение о природе математики и вычислений.
Наследие Тьюринга
Алан Тьюринг прожил короткую жизнь — он умер в 1954 году в возрасте всего 41 года при трагических обстоятельствах. Но его идеи живут и развиваются. Каждый раз, когда вы запускаете программу на компьютере, вы используете принципы, заложенные Тьюрингом.
В его честь названа высшая награда в области информатики — премия Тьюринга, которую часто называют «Нобелевской премией для программистов». А машина Тьюринга до сих пор остаётся основным инструментом для понимания того, что такое алгоритм и каковы фундаментальные возможности и ограничения вычислений.
Когда вы готовитесь к ЕГЭ по информатике и решаете задачи на алгоритмы, помните: все эти концепции восходят к работам гениального чудака, который ездил на велосипеде в противогазе и изменил мир.