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