Машина Тьюринга
Строгий ответ на вопрос «что такое алгоритм». 11 класс, углублённый
уровень — пара двенадцатая.
Уроки 23–24 поурочного плана: «Формализация понятия алгоритма. Машина Тьюринга
как универсальная модель вычислений. Тезис Чёрча—Тьюринга» и практическая работа
«Составление простой программы для машины Тьюринга».
Зачем алгоритму строгое определение
«Понятная последовательность шагов для исполнителя» годится,
пока алгоритм нужно написать.
Но чтобы доказать, что для задачи алгоритма нет вовсе, нужно точно
знать, что такое алгоритм: перебрать «все понятные инструкции» нельзя.
Уточнения появились в 1930-х: машина Тьюринга (1936),
машина Поста, рекурсивные функции, позже — нормальные алгорифмы Маркова. Все они
оказались равносильны: что вычисляет одна модель, вычисляют и другие.
Устройство машины
Лента — бесконечная в обе стороны, разбита на клетки; в каждой клетке
один символ алфавита. Пустая клетка — символ λ: им занята вся лента,
кроме конечного числа клеток.
Головка видит одну клетку.
Один такт
- записать символ в клетку под головкой;
- сдвинуть головку: L — влево, R — вправо, N — на
месте;
- перейти в новое состояние.
Состояния q1, q2, … — «память» машины. q1 —
начальное, q0 — остановка. Машину останавливает только переход в q0, а не
пустая клетка и не край слова.
Программа — таблица
Строка — состояние, столбец — символ под головкой, в клетке —
команда: что записать, куда сдвинуть, в какое состояние перейти.
Клетка «q1, 0» содержит 
: видим 0 — пишем 1, шаг вправо,
остаёмся в q1.
Эта машина идёт вправо, меняя 0 на 1 и 1 на 0, и
останавливается на первой пустой клетке:
→
.
Что делать на такте, решают только состояние и символ под головкой — не
вся лента.
Как выполнять вручную: столбиком
Пиши по такту: состояние, что видим, команда — и ленту после такта. Такт — одна
выполненная команда; последняя, переводящая в q0, тоже считается.
Такты на длинном слове
На ленте n единиц, головка над самой левой. Сколько тактов при n = 60? По
тактам не пройти.
Прогони на 1, 2, 3 единицах и посмотри на прирост:
Каждая новая единица добавляет одно и то же число тактов
a — тактов a·n + b. Обычно a — это число проходов по слову.
Стёртая команда: подставь и прогони
Задача: машина должна делать известное, но одна команда в таблице стёрта. Какую
поставить?
- Подставь вариант на место знака «?».
- Прогони машину на коротком слове из двух-трёх символов.
- Сверь ленту после остановки с тем, что должно получиться.
Неверный вариант выдаёт себя: машина встала (на этот
случай нет команды), зациклилась или после остановки на ленте не то
слово.
Что делает машина: прогони и сравни
- Возьми короткое слово, на котором все описания дают разное.
- Прогони машину по тактам.
- Сравни ленту после остановки с каждым описанием — совпадёт ровно одно.
Слово из одного символа часто не различает варианты:
«заменить каждый символ» и «заменить первый» на
дают одно и то же.
Бери три-четыре символа.
Универсальная машина и тезис Чёрча—Тьюринга
Универсальная машина Тьюринга получает на ленте описание
другой машины и её входное слово и делает то же, что та. Это прообраз компьютера, где
программа хранится в памяти рядом с данными.
Тезис Чёрча—Тьюринга: всё, что вычислимо по
алгоритму в интуитивном смысле, вычислимо на машине Тьюринга.
Это не теорема: «интуитивный алгоритм» строго не определён, поэтому
тезис нельзя доказать — его можно только опровергнуть, а этого не случилось.
Своя программа: как записать
дописать единицу к ряду
По одной команде в строке: состояние, что видим, что пишем, сдвиг, новое
состояние. Пустая клетка — λ или _. Стрелка и комментарий после # — по
желанию.
Дойти до конца слова — команда, которая
переписывает символ сам в себя со сдвигом R в том же состоянии. Запомнить
символ — перейти в своё состояние для каждого символа.
На каждую пару «состояние, символ», которая встретится,
нужна команда, иначе машина встанет. И хоть одна команда должна вести в
q0.
Что верно, а что нет
Верно
- За такт головка сдвигается не больше чем на клетку.
- На некоторых словах машина может не остановиться никогда.
- Пустой символ λ входит в алфавит машины.
Неверно
- «Лента конечна». Бесконечна в обе стороны.
- «Машина останавливается на пустой клетке». Только в q0.
- «Тезис Чёрча—Тьюринга — доказанная теорема».
- «Алфавит — только 0 и 1». Любой конечный набор символов.
Что делаем дальше
- Обзорный практикум — шесть задач, все сразу на странице, в любом
порядке: понятия, выполнить программу, такты на длинном слове, стёртая
команда, что делает машина и своя программа.
- Такты — столбиком на черновике, как на слайдах.
- Свою программу страница выполняет на всех коротких словах и
показывает, на каком слове машина ошиблась; исправляй и проверяй снова.
Отметка: закрыто 6 из 6 — «5», 5 — «4», 3 или 4 — «3». В первых пяти вопросах
ответ — целое число.
За работу
Практикум «Машина Тьюринга» — в общей папке и на сайте. Не успел на
уроке — пройди дома: вариант будет другой, сдаётся тем же кодом.
Карточку в тетрадь можно взять с собой: на ней устройство машины, таблица
программы, такты на длинном слове и запись своей программы.