W9. Машины Тьюринга, теория автоматов, Алан Тьюринг и исторические предпосылки вычислений

1. Краткое содержание

1.1 Введение в теорию автоматов

1.1.1 Слово «автомат»

Слово automaton (мн. ч. automata) происходит от греч. αὐτόματον — «самодвижущийся», то есть действующий сам по себе. Оно вошло в латынь, а затем в современные европейские языки через латинизацию. Примечательно, что его впервые употребил Гомер (ок. 850 г. до н. э.), древнегреческий поэт, которому приписывают авторство «Илиады» и «Одиссеи» — древнейших известных литературных памятников Европы. В «Илиаде» Гомер описывает двери, открывающиеся сами собой, самоходные колёсные треноги и ожившие статуи. Идея машин, действующих без участия человека, столь же древна, как и само воображение человечества.

1.1.2 Что такое теория автоматов?

Теория автоматов — раздел теоретической информатики, в котором изучают:

• абстрактные математические машины (автоматы) и их возможности;
• вычислительные задачи, которые эти машины могут решать.

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

Есть две основные причины изучать теорию автоматов:

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

1.2 Модели вычислений

Модель вычислений — математическая схема, описывающая:

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

Модели вычислений изучают на трёх уровнях:

• Теория: теория автоматов, вычислимость, сложность вычислений.
• Практика: спецификация систем, построение компиляторов.

Существует много разных моделей. Основные семейства:

• Последовательные модели — выполняют по одному шагу:
  • конечные автоматы (FSA)
  • автоматы с магазином (PDA)
  • машины Тьюринга (TM)
• Функциональные модели — вычисление как вычисление математической функции:
  • λ-исчисление (Алонзо Чёрч, 1936)
• Параллельные / конкурентные модели — одновременная работа нескольких процессов:
  • сети Петри

Этот список не исчерпывающий; существуют сотни других моделей.

1.3 Иерархия Хомского: карта языков

Разные модели вычислений распознают разные классы языков. Иерархия Хомского упорядочивает эти классы от наиболее слабых (ограниченных) к наиболее мощным:

Иерархия Хомского: вложенные классы формальных языков и соответствующие им модели машин

Смысл этой схемы:

• Регулярные языки — распознаются FSA. FSA могут «считать» только до фиксированного числа (конечное число состояний — никакого произвольного ). Они справляются с шаблонами вроде «все строки, содержащие ab», но не с .
• Контекстно-свободные языки — распознаются PDA. PDA справляются с за счёт стека. Однако PDA в общем случае не замкнуты относительно пересечения: если стек «настроен» под один шаблон, одновременно проверить другой нельзя. Поэтому выходит за пределы PDA — память стека разрушительная (снятый символ теряется).
• Рекурсивно перечислимые языки — распознаются машинами Тьюринга. TM справляются с , потому что память на ленте неразрушительная: записанные символы остаются и могут многократно перечитываться.

1.4 Конечные автоматы (FSA): напоминание

Конечный автомат (FSA) — простейшая последовательная модель. Формально полный (детерминированный) FSA — это 5‑кортеж:

где:

• — конечное множество состояний;
• — конечный входной алфавит;
• — (полная) функция переходов;
• — начальное состояние;
• — множество принимающих состояний.

Главное ограничение: у FSA только фиксированная конечная память — текущее состояние. Нельзя сосчитать до произвольного , поэтому языки вроде недостижимы.

Применения FSA:

• Лексический анализ в компиляторах — сканирование исходного кода на лексемы (ключевые слова, идентификаторы, числа). Это первая фаза компиляции.
• Машины Мура/Мили — моделирование схем и электронных устройств. Машины Мили — это конечные преобразователи состояний с входной и выходной лентой.
• Проектирование и верификация систем — в UML state machines используется та же нотация для реактивных систем (например, контроллер температуры с состояниями Idle, Heating, Cooling, Error).
• Model checking ПО — автоматическая верификация реальных программ через построение конечных моделей. За эту технику была присуждена премия Тьюринга.

Пример — турникет с оплатой монетой: у турникета два состояния: Locked (заперт) и Unlocked (открыт). Вставка монеты ведёт из Locked в Unlocked; нажатие (толчок) — из Unlocked обратно в Locked. Любое другое действие (толчок в запертом состоянии, монета при уже открытом) даёт петлю на месте.

FSA турникета с оплатой монетой

FSA и верификация программ: задача верификации программ — даны программа и спецификация ; выполняет ли условие ? — в общем случае неразрешима (следствие теоремы Райса, её разберём позже). Если же сузить модель вычислений с полной машины Тьюринга до FSA, задача верификации становится разрешимой. В этом идея model checking: обменивать выразительность на разрешимость.

1.5 Автоматы с магазином (PDA): напоминание

Автомат с магазином (PDA) расширяет FSA стеком. Формально детерминированный PDA — это 7‑кортеж:

где:

• — конечное множество состояний;
• — конечный входной алфавит;
• — конечный алфавит магазина;
• — (частичная) функция переходов;
• — начальное состояние;
• — начальный символ магазина (маркер дна стека);
• — множество принимающих состояний.

PDA распознают контекстно-свободные языки; на этой модели строится синтаксический анализ в компиляторах — вторая фаза, которая проверяет, образуют ли лексемы корректную программу по грамматике.

Главное ограничение PDA: стек — разрушительная память. После снятия символа он исчезает. Поэтому PDA не может одновременно проверить два независимых счётных ограничения — для уже нужна машина Тьюринга.

1.6 Машина Тьюринга: формальное определение

1.6.1 Мотивация

Машина Тьюринга (TM) — наиболее мощная последовательная модель вычислений. Она расширяет PDA, заменяя разрушительный стек лентой чтения/записи — потенциально бесконечной последовательностью ячеек с символами, над которыми головка может сдвигаться влево, вправо или оставаться на месте и перезаписывать любую ячейку. В отличие от стека (доступ только к вершине), лента позволяет многократно перечитывать ранее записанное.

TM была предложена Аланом Тьюрингом в 1936 году, чтобы дать точное математическое определение «что можно вычислить». Она намеренно проста — достаточно проста для теоретических рассуждений — и при этом достаточно мощна, чтобы симулировать любой современный язык программирования.

1.6.2 Формальное определение

(Детерминированная) машина Тьюринга с лентами памяти — это 7‑кортеж:

where:

• — конечное множество состояний;
• — входной алфавит — символы, которые могут появляться на входной ленте;
• — алфавит памяти — символы, которые можно записывать на ленты памяти (заметьте: и могут различаться);
• — функция переходов (см. ниже);
• — начальное состояние;
• — начальный символ памяти — символ, изначально записанный на каждой ленте памяти (по аналогии с PDA его называют символом дна стека);
• — множество финальных (принимающих) состояний.

Сравнение определений FSA, PDA и TM:

Компонент	FSA	PDA	TM
Состояния	✓	✓	✓
Входной алфавит
Доп. алфавит памяти	—	(стек)	(лента)
Начальный символ памяти	—
Функция переходов	полная	частичная	частичная
Принимающие состояния	✓	✓	✓

1.6.3 Функция переходов

Для TM с лентами памяти функция переходов имеет вид:

Разбор по частям:

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

Три направления движения головки:

• — на право на одну позицию;
• — на лево на одну позицию;
• — стоять (не двигаться).

Важные замечания:

• Функция переходов частичная: для некоторых комбинаций «состояние–вход» переход не задан. Если машина попадает в конфигурацию без применимого перехода, будучи не в финальном состоянии, она отвергает вход.
• Из финальных состояний нет исходящих переходов: достигнув финального состояния, машина останавливается.
• Символ — специальный пустой символ (blank), обозначающий пустые ячейки. Ленты мыслятся бесконечными и заполненными пустыми символами за пределами записанного содержимого.

Для одноленточной TM () функция переходов упрощается до:

1.6.4 Переходы на рисунке

Переход из состояния в состояние изображают помеченной стрелкой:

где:

• и ;
• — входной символ, прочитанный с входной ленты;
• — символ, прочитанный с -й ленты памяти;
• — символ, записанный на -ю ленту памяти (вместо );
• — направление движения головки входной ленты;
• — направление движения головки -й ленты памяти;

при .

Графическое изображение перехода TM: чтение входа i, символов лент A₁…Aₖ, запись A’₁…A’ₖ, движение головок M₀…Mₖ

1.6.5 Конфигурации

Конфигурация (снимок) TM в данный момент фиксирует всё, что нужно, чтобы продолжить вычисление: текущее состояние, содержимое всех лент и положение каждой головки.

Для TM с лентами памяти конфигурация — это ‑кортеж:

где:

• — текущее состояние;
• задаёт входную ленту: — содержимое слева от головки, при — содержимое справа (и под головкой). Символ отмечает положение головки;
• аналогично задаёт -ю ленту памяти;
• — специальный маркер, используемый только в записи конфигураций (это не символ ленты).

Зачем нужны конфигурации: записав последовательность , можно проследить вычисление TM по шагам. Так обычно объясняют и проверяют поведение TM.

1.6.6 Условие принятия

Пусть даны TM и входная строка . Говорим, что принимается машиной , если:

то есть из начальной конфигурации за конечное число шагов можно попасть в финальную конфигурацию .

Начальная конфигурация :

Головка входной ленты в начале строки ; на каждой ленте памяти в начале символ .

Финальная конфигурация :

Конфигурация финальна тогда и только тогда, когда текущее состояние лежит в .

Язык, принимаемый машиной :

1.7 Примеры машин Тьюринга

1.7.1 Пример: распознавание

Это одноленточная TM (). Стратегия:

1. Использовать ленту памяти как счётчик: за каждый a на входе записывать маркер M на ленту памяти.
2. Когда на входе начинаются b, двигать головку памяти назад и снимать по одному M на каждый b.
3. Принять вход, если он заканчивается ровно в момент, когда головка памяти вернулась к .

Диаграмма состояний:

TM для языка aⁿbⁿ (n > 0): состояния q₀, q₁, q₂ и финальное qF

Трассировка для входа aabb:

Имеем , значит aabb принимается.

Как читать трассу: в каждой конфигурации символ сразу после на входной ленте — тот, что сейчас под головкой входа. На ленте памяти символ сразу после — под головкой памяти. Когда головка памяти доходит до после снятия всех маркеров M, машина переходит в .

1.7.2 Пример: распознавание

Этот язык нельзя распознать PDA (классический контекстно-зависимый пример), зато с ним справляется TM. Стратегия обобщает предыдущую: на ленте памяти считаем a, затем проверяем столько же b (снимая маркеры), затем столько же c (перечитывая и снимая оставшиеся маркеры).

Диаграмма состояний:

TM для языка aⁿbⁿcⁿ (n > 0): состояния от q₀ до q₃ и финальное qF

Частичная трассировка для входа aabbcc (начиная после фазы чтения b):

Вход aabbcc принимается.

Почему в головка памяти движется вправо (а не влево): на фазе чтения a () головка памяти идёт вправо, записывая по одному M на каждый a. На фазе чтения b () головка идёт влево, снимая по одному M на каждый b. Войдя в (при первом c), головка снова у . Дальше снова движение вправо, снимая по одному оставшемуся M на каждый c. Такое повторное использование ленты и делает TM мощнее PDA.

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

Тезис Чёрча — Тьюринга (его также называют тезисом Тьюринга) утверждает:

Функция на натуральных числах может быть вычислена эффективным методом тогда и только тогда, когда она вычислима на машине Тьюринга.

«Эффективный метод» означает алгоритм: конечную, детерминированную, пошаговую процедуру, которая всегда завершается с правильным ответом. Этот тезис не теорема — его нельзя формально доказать, потому что «эффективный метод» — неформальное понятие. Но более 80 лет он выдерживает проверку: любая предложенная модель вычислений (λ-исчисление, рекурсивные функции, современные CPU, Python, Haskell, …) оказывается по выразительной силе эквивалентна машинам Тьюринга.

Следствие для программирования: любую функцию, вычислимую на современном языке программирования, можно вычислить на TM, и наоборот. У TM и языков высокого уровня одинаковая выразительная сила. TM не предназначены для практического программирования — они нужны для доказательств: с ними проще рассуждать из-за простоты.

1.9 Алан Тьюринг: жизнь и наследие

Алан Тьюринг (23 июня 1912 — 7 июня 1954) — британский математик, логик и учёный в области вычислений. Он внёс фундаментальный вклад в четыре разные области:

• Вычислимость — машина Тьюринга и ответ на Entscheidungsproblem.
• Криптография — взлом немецкой шифровальной машины Enigma во Второй мировой войне.
• Искусственный интеллект — тест Тьюринга.
• Биоинформатика — математическое моделирование формирования биологических узоров.

Тьюринг жил и умер в Уилмслоу, недалеко от Манчестера (Великобритания); там синяя мемориальная доска гласит: «Основатель информатики и криптограф, чья работа была ключом к взлому военных шифров Enigma».

1.9.1 Вычислимость и машина Тьюринга

В 1936 году Тьюринг опубликовал работу «On Computable Numbers, with an Application to the Entscheidungsproblem» — одну из важнейших статей в истории математики. В ней он ввёл машину Тьюринга как математическую модель вычислений и показал, что у задачи разрешимости Гильберта нет общего алгоритмического решения (см. раздел 1.12).

1.9.2 Криптография: взлом Enigma

Во Вторую мировую войну Тьюринг работал в Government Code and Cypher School (GC&CS) в Блетчли-парке — центре британской криптоаналитики. Он возглавлял Hut 8, отдел, отвечавший за взлом немецких морских шифров.

Ключевые моменты этой истории:

• Enigma — немецкая электромеханическая шифровальная машина. Каждое сообщение шифровалось с ежедневно меняющимся ключом, давая на вид случайные символы.
• Польские математики уже выяснили основные принципы чтения сообщений Enigma и передали сведения британцам до войны.
• С началом войны Германия ежедневно меняла шифросистему, и старые методы перестали работать.
• Алан Тьюринг и Гордон Уэлчман спроектировали Bombe — электромеханическую машину, автоматически перебиравшую возможные настройки Enigma. К середине 1940 года сигналы люфтваффе регулярно читались.

Важный урок: за любым крупным достижением всегда стоит коллектив. Как документирует племянник Алана Дермот Тьюринг в книге «X, Y and Z: The Real Story of How Enigma Was Broken», заслуга принадлежит широкому сообществу — включая польских математиков, — а не одному гению в одиночку.

1.9.3 Искусственный интеллект: тест Тьюринга

В 1950 году Тьюринг опубликовал статью «Computing Machinery and Intelligence» в журнале Mind. Она начинается вопросом:

«Я предлагаю рассмотреть вопрос: могут ли машины мыслить?»

Поскольку «мышление» — слишком размытое понятие для прямой проверки, Тьюринг предложил игру в имитацию (сейчас её называют тестом Тьюринга):

• Человек-следователь (C) текстом общается с двумя скрытыми участниками: компьютером (A) и человеком (B).
• Следователь задаёт вопросы и пытается понять, кто есть кто.
• Если компьютер стабильно вводит следователя в заблуждение, заставляя думать, что он человек, машину считают интеллектуальной.

Тест Тьюринга (игра в имитацию): следователь C пытается отличить компьютер A от человека B по тексту

Тьюринг также отвечал на возражение леди Лавлейс — идею, что «машина может делать только то, что мы ей приказываем». Он считал, что возражение заслуживает серьёзного рассмотрения, но не опровергает возможность машинного интеллекта.

1.9.4 Биология и математический морфогенез

В 1952 году Тьюринг опубликовал «The Chemical Basis of Morphogenesis» — теперь это считают одной из основополагающих работ математической биологии. Он предположил, что сложные узоры у живых организмов — полосы зебры, пятна леопарда, расположение лепестков — могут возникать из простого математического механизма: систем реакции–диффузии.

Два химических вещества (он назвал их морфогены) диффундируют в ткани и реагируют друг с другом. При определённых условиях малые случайные флуктуации самопроизвольно усиливаются до устойчивых периодических структур. Это было биоинформатикой до биоинформатики — задолго до того, как у области появилось имя.

1.10 Исторический контекст: от людей-вычислителей до машин с хранимой программой

1.10.1 Люди-компьютеры

До электронных компьютеров слово computer обозначало человека, выполнявшего расчёты. В XIX — начале XX века (примерно до 1946 года) крупные организации содержали целые комнаты людей-вычислителей:

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

Так выглядела «бумажно-карандашная» индустриализация математики. Труд был монотонным и подверженным ошибкам.

1.10.2 ENIAC и первые компьютеры

Перелом произошёл в 1945 году с ENIAC (Electronic Numerical Integrator and Computer) — первым программируемым электронным универсальным цифровым компьютером.

• Ввод в ENIAC шёл через перфокарты — физические карты с отверстиями, кодирующими данные.
• Ранние программы вводили вручную, соединяя кабели (как на телефонной коммутаторной доске).
• Операторами ENIAC была команда женщин, ранее работавших людьми-вычислителями; они стали первыми в мире программистами электронных компьютеров.

1.10.3 Компьютер с хранимой программой

Ключевой концептуальный шаг — компьютер с хранимой программой: машина, в которой и команды программы, и данные лежат в одной памяти, а программу можно менять, изменяя память, а не перекоммутируя оборудование. Контрастируйте с ткацким станком Northrop, который всегда выполняет одну и ту же «программу ткачества», зашитую в физическую конструкцию.

1.10.4 Архитектура фон Неймана

Архитектура фон Неймана (имени Джона фон Неймана) — доминирующая модель компьютеров с хранимой программой:

• Центральный процессор (CPU), включающий:
  • устройство управления — выборка и декодирование команд из памяти;
  • арифметико-логическое устройство (ALU) — арифметические и логические операции.
• Блок памяти — хранит и данные, и команды программы в едином адресном пространстве.
• Устройства ввода и вывода.

Архитектура фон Неймана: устройство управления и ALU разделяют общую память для программы и данных

1.10.5 Гарвардская архитектура

Гарвардская архитектура разделяет пути хранения и сигналов для команд и данных на физически разные памяти:

• Память команд — хранит код программы; CPU только читает отсюда.
• Память данных — хранит значения; CPU читает и пишет.
• ALU, устройство управления и ввод-вывод — отдельные блоки с выделенными шинами.

Гарвардская архитектура: физически раздельные памяти для команд и данных

Главное отличие от фон Неймана: в гарвардской схеме нет риска случайно перезаписать команды данными (и наоборот), и CPU может одновременно выбирать команду и читать данные по разным шинам. Современные микроконтроллеры и DSP часто используют эту архитектуру.

1.10.6 TM и машины фон Неймана

TM и машины фон Неймана (VNM) эквивалентны по выразительной силе — они вычисляют один и тот же класс функций. Разница в доступе к памяти:

• TM: последовательный доступ — головка движется по ленте шаг за шагом.
• VNM: прямой (произвольный) доступ — к любому адресу памяти за один шаг.

Это различие не меняет класс разрешимых задач. Оно может влиять на вычислительную сложность (число шагов), но не на саму вычислимость. TM может симулировать VNM и наоборот.

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

1.11 Общая модель многоленточной TM

Наиболее общая форма TM имеет:

• одну входную ленту — только чтение, головка движется влево/вправо;
• одну выходную ленту — только запись, головка движется вправо;
• лент памяти — чтение/запись, головки движутся влево/вправо/стоят.

Все головки управляются одним конечным автоматом (функцией переходов ). Это стандартная теоретическая модель в теории сложности.

В нашем курсе в основном работаем с TM с одной лентой памяти, для которых функция переходов имеет вид:

1.12 Математическая логика и Entscheidungsproblem

1.12.1 Principia Mathematica и мечта о формализации

В начале XX века математики стремились поставить всю математику на прочный логический фундамент. Бертран Рассел и Альфред Норт Уайтхед опубликовали Principia Mathematica (1910–1913) — монументальный труд на ~2000 страниц, в котором предпринималась попытка:

• аксиоматизировать всю математику — вывести любую истину из небольшого набора логических аксиом;
• доказать, что система полна (всякая истинная формула выводима) и непротиворечива (ложные формулы недоказуемы).

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

1.12.2 Программа Гильберта и Entscheidungsproblem

Давид Гильберт (1862–1943) — один из самых влиятельных математиков своей эпохи. В 1900 году он опубликовал 23 нерешённые задачи — дорожную карту математики XX века. В 1928 году вместе с Вильгельмом Аккерманом он сформулировал Entscheidungsproblem («проблему разрешимости»):

Найти алгоритм, который по данным предпосылкам — формулам логики первого порядка — и данному заключению определяет, выводимо ли это заключение из предпосылок по правилам логики первого порядка.

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

Entscheidungsproblem: существует ли универсальный алгоритм, разрешающий любую математическую истину?

1.12.3 Крах программы: Гёдель и Тьюринг

Мечта о полной, непротиворечивой и разрешимой математике рухнула под ударом двух последовательных результатов:

1. Курт Гёдель (1931) — теоремы о неполноте: любая логическая система достаточной выразительности (способная выразить элементарную арифметику) неполна: существуют истинные утверждения, которые нельзя доказать внутри системы. Полнота и непротиворечивость не могут выполняться одновременно. Математику нельзя полностью аксиоматизировать.

   Сам Тьюринг отмечал связь, писал в статье 1936 года: «выводы поверхностно сходны с выводами Гёделя».

2. Чёрч и Тьюринг (1936) — неразрешимость Entscheidungsproblem: независимо Алонзо Чёрч (через λ-исчисление) и Алан Тьюринг (через машины Тьюринга) доказали, что общего алгоритма для проблемы разрешимости не существует. Доказательство Тьюринга строит конкретную задачу — проблему остановки — и показывает, что её нельзя разрешить ни одной TM.

Связь с верификацией программ: это напрямую касается разработки ПО. Задача верификации программ — даны и спецификация ; удовлетворяет ли условию ? — эквивалентна вопросу, принимает ли TM определённый язык. Теорема Райса (будет позже) формулирует это так: любое нетривиальное семантическое свойство программ неразрешимо.

Формально:

программаспецификацияформулагопорядка ВыполняетсялиНЕРАЗРЕШИМО

Однако при ограничении модели вычислений с полной TM до конечного автомата задача верификации становится разрешимой. В этом смысл model checking — техники, удостоенной премии Тьюринга.

1.12.4 Тьюринг, Гёдель и бесконечность

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

• «Если у нас есть хоть одно свойство — пусть даже тривиальное, — которого нет у машин Тьюринга, то мы не можем быть просто машинами Тьюринга».

Это соприкасается с теорией бесконечных множеств (числа Кантора) и философией сознания — вопросами, которые работа Тьюринга подняла, но не решила; они по-прежнему активно обсуждаются.

---

2. Определения

• Automaton (автомат): абстрактная математическая машина, обрабатывающая входные символы и переходящая между состояниями по правилам.
• Automata Theory (теория автоматов): раздел теоретической информатики об абстрактных машинах (автоматах) и вычислительных задачах, которые они решают.
• Turing Machine (TM, машина Тьюринга): математическая модель вычислений: конечное множество состояний, входная лента, одна или несколько лент памяти с чтением/записью и функция переходов. Сильнейшая последовательная модель; задаёт границу алгоритмической вычислимости.
• Finite State Automaton (FSA): 5‑кортеж , распознающий регулярные языки при фиксированной конечной памяти (текущее состояние). Не может сосчитать до произвольного .
• Pushdown Automaton (PDA): 7‑кортеж , расширяющий FSA стеком LIFO; распознаёт контекстно-свободные языки.
• Input Alphabet ( или ): конечное множество символов входной ленты.
• Memory Alphabet (): конечное множество символов, записываемых на лент(ы) памяти TM или PDA; отличается от входного алфавита.
• Blank Symbol (): специальный символ () для пустых ячеек; ленты бесконечны и заполнены пустыми ячейками за пределами записи.
• Initial Memory Symbol (): символ в начале каждой ленты памяти при старте TM; маркер дна ленты.
• Transition Function (): частичная функция, задающая поведение TM: по текущему состоянию и символам под головками — следующее состояние, новые символы и движения головок.
• Configuration (Snapshot) (конфигурация): ‑кортеж — полное состояние TM: состояние, ленты, положения головок.
• Initial Configuration () (начальная конфигурация): , где — входная строка.
• Final Configuration () (финальная конфигурация): любая конфигурация с состоянием .
• Acceptance (принятие): строка принимается TM , если — за конечное число шагов достижима финальная конфигурация.
• (отношение шага): один шаг вычисления TM ( — за один шаг из в ).
• (рефлексивно-транзитивное замыкание): ноль или более шагов.
• Chomsky Hierarchy (иерархия Хомского): классификация формальных языков по выразительной силе: регулярные (FSA) КС (PDA) рекурсивно перечислимые (TM).
• Church–Turing Thesis (тезис Чёрча — Тьюринга): неформальное утверждение, что всякая эффективно вычислимая функция вычислима на TM. Не теорема (формально не доказывается), но общепринято.
• Entscheidungsproblem: проблема разрешимости Гильберта (1928): существует ли алгоритм, который по любому математическому утверждению определяет, выводимо ли оно из аксиом? Ответ: нет (Чёрч, Тьюринг, 1936).
• Gödel’s Incompleteness Theorems (теоремы Гёделя о неполноте): два результата (1931): любая достаточно мощная формальная система либо неполна (есть недоказуемые истины), либо противоречива (доказуемы ложные утверждения).
• Turing Test (Imitation Game) (тест Тьюринга): критерий «интеллекта» машины (1950): если компьютер вводит человека-следователя в заблуждение, его считают интеллектуальным.
• Model Checking: автоматическая проверка, удовлетворяет ли конечная модель системы спецификации. Разрешимо (в отличие от общей верификации программ), так как модель ограничена уровнем FSA.
• Von Neumann Architecture: архитектура с единой памятью для команд и данных и CPU (устройство управления + ALU).
• Harvard Architecture: архитектура с физически раздельными путями и памятью для команд и данных; возможна одновременная выборка команды и доступ к данным.
• Stored-Program Computer: компьютер, в котором команды хранятся в памяти и могут изменяться (в отличие от жёстко «прошитых» программ).
• Reaction-Diffusion System (система реакции–диффузии): модель Тьюринга (1952) биологических узоров: два морфогена диффундируют и реагируют, порождая периодические пространственные структуры (полосы, пятна).

---

3. Формулы

• Определение TM ( лент):
• Функция переходов ( лент памяти):
• Функция переходов (1 лента памяти):
• Конфигурация ( лент памяти):
• Начальная конфигурация:
• Условие принятия: , где при
• Язык TM:
• Определение FSA: с
• Определение PDA: с

---

4. Примеры

4.1. Спроектировать TM для (Лаба 8, Задание 1)

Спроектируйте машину Тьюринга, распознающую . Язык состоит из строк, где непустое слово над повторяется дважды, разделённые символом c. Примеры: aca (), abcab (), bcb (). Опишите стратегию и ключевые переходы.

Показать решение

Идея: чтобы проверить , копируем первую половину в память, затем посимвольно сравниваем вторую половину с памятью.

Стратегия TM для wcw: копирование левого блока, затем сравнение с правым

Стратегия (1 лента памяти):

1. Фаза копирования (): читать символы до c с входа, записывая каждый на ленту памяти. Обе головки движутся вправо.
2. Фаза перемотки (): при встрече c вернуть головку памяти к (перемотка).
3. Фаза сравнения (): синхронно двигать вход и память вправо, сравнивая символы.
4. Принятие (): если одновременно на входе и в памяти достигнут пустые ячейки.

Ключевые переходы:

• — копировать a в память.
• — копировать b в память.
• — разделитель; начать перемотку памяти.
• при — перемотка памяти.
• — память в начале; начать сравнение.
• — совпадение a.
• — совпадение b.
• — обе ленты исчерпаны: принять.
• Любое несовпадение: перехода нет; отвергнуть.

Ответ: TM записывает первую половину в память, перематывает, затем посимвольно сравнивает. Принимает тогда и только тогда, когда строка имеет вид с одинаковыми половинами.

4.2. Спроектировать TM для (Лаба 8, Домашнее задание 1)

Спроектируйте TM, распознающую — строки из нуля и более повторений ab: , ab, abab, ababab, …

Показать решение

Идея: — на самом деле регулярный язык; его распознаёт FSA с тремя состояниями. TM может использовать ту же логику конечного управления. Лента памяти не нужна.

Вид конечного управления TM для языка (ab)ⁿ

Наглядно как у FSA:

• Состояние (старт, принимающее): ожидается a или конец строки.
• Состояние : только что прочитан a, ожидается b.
• Любой другой символ ведёт в мёртвое (отвергающее) состояние.

Переходы TM (лента памяти не нужна или игнорируется):

• — пустой вход: принять ().
• — прочитан a, переход в .
• — после a прочитан b, возврат в .
• Все прочие переходы: не определены (отвергнуть).

Вернувшись в после чтения b, если вход пуст: принять. Иначе продолжать.

Ответ: TM чередует ожидание a (состояние ) и b (). Принимает тогда и только тогда, когда вход заканчивается в (все пары завершены). Для этого регулярного языка лента памяти не нужна.

4.3. Спроектировать TM для (Лаба 8, Задание 2)

Спроектируйте TM, распознающую , где — обращение строки . Примеры: abcba (), bcb (). Опишите стратегию и ключевые переходы.

Показать решение

Идея: проверяют, копируя в память (слева направо), затем читая вторую половину входа при движении по памяти справа налево — ведь , читаемое слева направо, согласуется с , читаемым справа налево.

Стратегия TM для wcwᴿ: сравнение второго блока с памятью в обратном направлении

Стратегия (1 лента памяти):

1. Фаза копирования (): читать символы до c, писать в память (обе головки вправо).
2. На c: оставить головку памяти на месте (сразу после последнего символа ), сдвинуть вход. Переход к фазе сравнения.
3. Фаза сравнения (): вход движется вправо (читается слева направо), память — влево (читается справа налево). На каждом шаге сравнение.
4. Принятие (): на входе пусто, в памяти у .

Ключевые переходы:

• — копировать a.
• — копировать b.
• — найден c; вход проходит c, память на шаг назад к последнему символу .
• — совпадение a: вход вправо, память влево.
• — совпадение b.
• — достигнуты оба конца: принять.

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

4.4. Спроектировать TM для (Лаба 8, Домашнее задание 2)

Спроектируйте TM, распознающую . Примеры: (), abbccc (), aabbbbcccccc (). Подробно опишите стратегию.

Показать решение

Идея: обобщение схемы для с соотношением . TM кодирует это соотношение прямо на ленте памяти, записывая разное число маркеров на каждый a.

Раскладка памяти TM для проверки языка aⁿb²ⁿc³ⁿ

Стратегия:

На каждый a на входе записываем на ленту памяти две маркеры B и три маркеры C. Далее:

• каждый b снимает одну маркер B;
• каждый c снимает одну маркер C;
• принимаем, когда одновременно исчерпаны вход и память.

Раскладка ленты памяти после чтения символов a:

Фазы:

1. Фаза a (): на каждый a записать в память BB + CCC (5 шагов по памяти на символ входа). Сдвинуть вход.
2. Фаза b (): на каждый b снять одну B с памяти (дойти вправо до следующей B, стереть).
3. Переход к фазе c: когда все B сняты (головка у первой C), перейти в .
4. Фаза c (): на каждый c снять одну C.
5. Принятие (): вход пуст и память пуста одновременно.

Ключевые переходы (схематично):

• записать B, сдвинуть память, записать B, сдвинуть память, записать C, C, C; затем сдвинуть вход; вернуться в .
• — первый b; начать снимать B.
• — снять следующую B.
• — все B сняты; начать снимать C.
• — снять следующую C.
• — принять.

Ответ: TM кодирует соотношение прямо в раскладке памяти. Техника обобщается на любой язык с фиксированными пропорциями : на каждый a писать маркеров B и маркеров C.

4.5. Спроектировать TM для палиндромов (Лаба 8, Задание 3)

Спроектируйте TM, распознающую палиндром. Палиндром читается одинаково слева направо и справа налево. Примеры: , a, b, aba, abba. Опишите стратегию.

Показать решение

Идея: для палиндрома . Проверку палиндрома можно свести к проверке вида , сохранив строку в памяти и сравнив её с обращением.

Стратегия TM для палиндрома: копия слова сравнивается с исходником при чтении входа назад

Стратегия (1 лента памяти):

1. Фаза копирования (): скопировать весь вход на ленту памяти (обе головки вместе вправо).
2. Перемотка памяти (): после полного чтения входа вернуть головку памяти к .
3. Фаза сравнения (): одновременно двигать головку памяти вперёд и головку входа назад, сравнивая символы.
4. Принятие (): головки встречаются в середине (или одновременно достигают и пустого символа).

Замечание: у TM головка входа может двигаться влево, в отличие от обычного FSA или PDA. Такой двунаправленный доступ — часть большей мощности TM.

Альтернатива — двухпроходное сравнение:

1. Найти центр строки (чередуя движения вперёд и назад).
2. Сравнивать первый символ с последним, второй с предпоследним и т. д.

Смысл: проверка палиндрома для эквивалентна проверке . Поскольку TM могут перечитывать ленты, это делается естественно: в памяти хранится ; после перемотки память читается вперёд, а вход сравнивается в обратном порядке.

Ответ: TM принимает тогда и только тогда, когда вход — палиндром. Лента памяти хранит копию , читаемую вперёд при сравнении с входом, читаемым назад.

4.6. Спроектировать TM для (Лаба 8, Задание 4)

Спроектируйте TM, распознающую . Объясните, почему здесь нужна TM (и почему одним детерминированным PDA это не обойти просто), и опишите стратегию TM.

Показать решение

Идея: для объединения нужно проверить два разных счётных условия. Детерминированный PDA не может сделать это за один проход: стек по-разному настраивается под каждую альтернативу. TM может перечитать ленту и по сути последовательно испробовать обе стратегии.

TM для {aⁿbⁿ} ∪ {aⁿb²ⁿ}: одна стратегия подсчёта, сброс, затем другая

Почему одному детерминированному PDA трудно: после чтения блока a и помещения маркеров в стек PDA должен решить, ожидать или символов b. В детерминированном случае решение нужно принять, ещё не видя b — это невозможно. Недетерминированный PDA мог бы «угадывать»; детерминированная TM может сначала проверить один вариант, затем другой.

Стратегия TM:

Фаза 1: проверка

1. На каждый a записать в память один M. Обе головки вправо.
2. На каждый b снять один M (память влево). Вход вправо.
3. Если вход кончился и память у : принять (случай : сразу пусто).
4. Если вход кончился, а в памяти ещё есть M: отвергнуть.
5. Если b кончились, а M ещё есть: перейти к фазе 2 (предварительно сброс).

Фаза 2: проверка

1. Сброс: перемотать память к ; вернуть головку входа в начало.
2. На каждый a записать один M в память.
3. На каждую пару b снять один M.
4. Если вход кончился, память у и число прочитанных b чётно: принять.
5. Иначе: отвергнуть.

Ответ: возможность TM перечитывать и перематывать ленты позволяет проверять несколько гипотез подряд. Это сила неразрушительного двунаправленного доступа к ленте — недоступного PDA с разрушительным однонаправленным стеком.

4.7. Трассировка TM на (Лекция 8, Пример 1)

Рассмотрим TM , распознающую , с переходами (1 лента памяти):

• (петля)
• (петля)

Выполните трассировку на входе . Выпишите все конфигурации .

Показать решение

Идея: на ленте памяти считаем a, записывая маркеры M. В каждой конфигурации символ отмечает положение головки.

Фазы управления при трассировке TM для aⁿbⁿ

1. Начальная конфигурация:
2. читает a, память читает : переход в , головка памяти вправо, головка входа на месте.
3. читает a, память читает _ (пусто): записать M, обе головки вправо.
4. читает a, память читает _: записать M, обе головки вправо.
5. читает b, память читает _: вход на месте, головка памяти влево. Переход в .
6. читает b, память читает M: вход вправо, головка памяти влево.
7. читает b, память сдвигается влево мимо .
8. читает _ (конец входа), память читает : переход в .

Имеем .

Ответ: строка aabb принимается. Машина записала 2 маркера M (по одному на каждый a), сняла их при чтении двух b и достигла , когда вход исчерпан, а головка памяти вернулась к .

4.8. Трассировка TM на (Лекция 8, Пример 2)

Рассмотрим TM , распознающую , с переходами:

Дайте частичную трассировку на входе , начиная с конфигурации .

Показать решение

Идея: к машине для добавлена третья фаза. После чтения всех b и возврата головки памяти к машина входит в и читает c, снова двигая головку памяти вправо — второй раз «съедая» маркеры M.

Трёхфазная TM для aⁿbⁿcⁿ

Начиная с :

1. читает b, память читает M: вход вправо, память влево.
2. читает b, память читает … головка памяти сдвинулась влево к .
3. читает c, память читает : переход в , головки на месте.
4. читает c, память читает M: вход вправо, память вправо.
5. читает c, память читает M: вход вправо, память вправо.
6. читает _, память читает _: переход в .

Ответ: строка aabbcc принимается. Лента памяти кодирует . Маркеры M проходятся один раз на фазе b (справа налево) и один раз на фазе c (слева направо). Вход и память исчерпываются одновременно.

4.9. Спроектировать TM для (Туториал 8, Пример 1)

Спроектируйте детерминированную машину Тьюринга, распознающую язык .

Показать решение

Идея: классический нерегулярный контекстно-свободный язык. TM справляется, используя ленту как счётчик — помечая согласованные пары и .

Цикл одноленточной TM для aⁿbⁿ

Идея: многократно сканировать ленту: пометить одну несопоставленную (заменить на ), затем найти вправо и пометить одну несопоставленную (заменить на ), вернуться влево. Принять, когда все символы помечены.

Состояния: (искать ), (искать вправо), (возврат влево), (принять), (отвергнуть).

Функция переходов:

Состояние	Чтение	Запись	Движение	Далее
			R
			R
			S
			R
			R	(пропуск помеченных )
			L
			S
			L
			L
			R

Условие принятия: в , если остались только (следующий непрочитанный — ), принять. Отвергнуть при несопоставленной или лишней .

Трасса на :

меткавозврат

Далее: пометить вторую → найти вторую → всё помечено → принять.

4.10. Спроектировать TM для (Туториал 8, Пример 2)

Спроектируйте TM, распознающую контекстно-зависимый язык .

(Замечание: этот язык не распознаётся ни конечным автоматом, ни автоматом с магазином — только машина Тьюринга.)

Показать решение

Идея: расширить схему для третьей фазой: на каждом проходе помечаются по одной , одной и одной .

Цикл одноленточной TM для aⁿbⁿcⁿ

Идея: на каждой итерации основного цикла: 1. Идти вправо, пометить крайнюю слева немаркированную символом . 2. Далее вправо — крайнюю немаркированную как . 3. Далее вправо — крайнюю немаркированную как . 4. Просканировать всю ленту влево к началу. 5. Повторять. Принять, когда не осталось немаркированных и все и тоже полностью помечены.

Состояния: (искать ), (искать ), (искать ), (возврат влево), (проверка: только и ), (принять).

Функция переходов (высокий уровень):

Состояние	Чтение	Запись	Движение	Далее
			R
			R	(пропуск помеченных )
			R	(больше нет — проверить остальное)
			R
			R	(пропуск помеченных )
			R
			R
			R	(пропуск помеченных )
			L
	любой	тот же	L	(скан до левого края)
			R
			R
			R
			S

Отвергнуть, если в какой-то момент не найден ожидаемый символ (например, нет или , когда они нужны).

Трасса на (кратко):

Проход 1: , , , возврат.

Проход 2: , , , возврат.

Проход 3: видит (больше нет ) → вход в → только и → принять.