Машина Тьюринга
Есть лента с символами, головка и таблица команд. Надо понять, что программа сделает с лентой. Шагать по большому числу не придётся, достаточно разгадать программу на маленькой ленте.
- 1Как устроена машина
- 2Читаем таблицу команд
- 3Две простые программы
- 4Как решать на экзамене
- 5Ловушки и домашка
Как устроена машина
- Лента разделена на ячейки. В каждой стоит символ:
0,1или пустой символλ. - Головка стоит над одной ячейкой.
- Состояние машины:
q0,q1и так далее. В начале этоq0. - Программа это таблица: строки это состояния, столбцы это символ под головкой, а в клетке команда.
Команда состоит из трёх частей через запятую: что записать, куда сдвинуться, в какое состояние перейти.
| Сдвиг | Что значит |
|---|---|
L | Влево |
R | Вправо |
N | Без сдвига |
S | Завершить работу после этой команды |
Например, команда 0, L, q3 записывает 0, сдвигает головку влево и переводит её в состояние q3. Сдвиг происходит после записи. Пустая клетка в таблице значит, что такой пары состояния и символа быть не может.
Читаем таблицу команд
На экзамене на ленте записано двоичное число, а слева и справа от него λ. Головка стоит рядом с числом. Ответом будет итоговая запись на ленте, переведённая в десятичную систему.
Вот программа. На ленте 101, головка в ближайшей ячейке справа от числа.
| λ | 0 | 1 | |
|---|---|---|---|
| q0 | λ, L, q1 | ||
| q1 | 1, S, q1 | 0, L, q1 | 1, L, q1 |
Проследим по шагам. Жирным выделена ячейка, над которой стоит головка.
| Шаг | Состояние | Лента | Команда |
|---|---|---|---|
| 1 | q0 | λ 1 0 1 λ | λ, L, q1 |
| 2 | q1 | λ 1 0 1 λ | 1, L, q1 |
| 3 | q1 | λ 1 0 1 λ | 0, L, q1 |
| 4 | q1 | λ 1 0 1 λ | 1, L, q1 |
| 5 | q1 | λ 1 0 1 λ | 1, S, q1 |
| Итог | 1 1 0 1 |
Программа прошла всё число, ничего в нём не меняя, и приписала единицу слева. Было 101, это 5, стало 1101, это 13. Теперь то же самое можно сделать с любым числом, не шагая по нему.
Две простые программы
Инвертировать все биты
Головка стоит на пустой клетке справа от строки. Нужно, чтобы все 0 стали 1, а все 1 стали 0.
| λ | 0 | 1 | |
|---|---|---|---|
| q0 | λ, L, q1 | ||
| q1 | λ, S, q1 | 1, L, q1 | 0, L, q1 |
Сначала один шаг с пустой клетки на последний символ. Потом идём влево и меняем каждый символ. Пустая клетка слева означает конец.
Пусть на ленте 250 нулей и 750 единиц в любом порядке. Сколько единиц будет после работы? Каждый ноль станет единицей, поэтому единиц станет 250, а нулей 750.
Та же программа. На ленте 300 нулей и 700 единиц. Сколько единиц будет на ленте после работы?
Прибавить 1 к двоичному числу
Головка стоит на последней цифре.
| λ | 0 | 1 | |
|---|---|---|---|
| q0 | 1, S, q0 | 1, S, q0 | 0, L, q0 |
Единицы справа превращаются в нули, это перенос. Первый ноль слева становится единицей, и машина останавливается. Если нулей не было, единица допишется в пустую клетку слева.
Та же программа. На ленте двоичная запись числа 47, головка на последней цифре. Какое число получится на ленте? Ответ запиши в десятичной системе.
Как решать на экзамене
- Выпиши таблицу и прогони её на 2–3 маленьких лентах из 2–3 символов.
- Сформулируй общее правило: «инвертирует», «прибавляет 1», «приписывает слева».
- Примени правило к большому числу. По шагам идти не нужно.
- Прогони программу руками на маленькой ленте ещё раз и сверь с правилом.
В настоящих задачах программы обычно делают что-то из этого:
| Что делает программа | Как это выглядит в таблице |
|---|---|
| Дописывает цифры слева или справа | Идёт по числу, ничего не меняя, потом пишет в клетки с λ |
| Прибавляет 1 | Единицы становятся нулями, первый ноль становится единицей |
| Меняет ведущую цифру и дописывает единицу слева | Доходит до λ, возвращается на шаг, меняет цифру и снова идёт влево |
Ловушки и домашка
| Ловушка | Как не попасться |
|---|---|
| Где стоит головка в начале | Справа или слева от числа, на последней цифре или рядом с ней. Читай условие |
| Что считают в ответе | Единицы, нули, длину ленты или число в десятичной системе |
| Порядок действий в команде | Сначала запись, потом сдвиг |
Команда с S | Символ из неё записывается, и только потом машина останавливается |
Домашка
Шесть задач с настоящих экзаменов и из банка ФИПИ. Описание исполнителя повторяется над каждой задачей. Сначала разгадай программу на ленте 101, потом примени правило к числу из условия.
В последней задаче головка стоит слева от числа, а не справа, как в остальных.
Примеры и задачи «Попробуй сам» учебные, в домашке задачи с настоящих экзаменов и из банка ФИПИ.