Каждый из нас лишь выиграет, создавая время от времени «игрушечные» программы с заданными искусственными ограничениями, заставляющими нас до предела напрягать свои способности. Искусство решения мини задач на пределе своих возможностей оттачивает наше умение для реальных задач.
Дональд Кнут (с)
Как известно, на машине Тьюринга (далее МТ) запрограммировать можно всё, что мы вообще считаем программируемым, но в реальности программы на МТ настолько громоздкие, что МТ редко используется даже в академических примерах. И тем не менее в некоторых отдельных случаях с помощью МТ получается написать небольшую программу, на КДПВ изображена программа из 5 состояний на алфавите из 3 символом. Если вы изучали программирование, то задачу, которую решает эта программа, вы скорее всего встречали. Если я сумел вас заинтересовать, то приглашаю в небольшое приключение по реверс инженирингу МТ.
Материал статьи предоставлен Владимиром Пинаевым
Напоминалка про МТ
Существует множество незначительно отличающихся друг от друга вариантов МТ, опишу используемый в этом эмуляторе, в котором можно будет и проверить
Алфавит
и специальный «пустой» символ λ.Конечное множество состояний
, начальное состояние 
.Правила перехода
. В соответствии с этими правилами паре (состояние, символ) сопоставляется тройка (новое состояние, символ, направление сдвига).
Такая программа применяется к бесконечной в обе стороны ленте, состоящей из ячеек с символами
Работа программы заключается в последовательном применении правил перехода к текущему состоянию и символу на текущей позиции ленты. Если текущие состояние системы — 
, символ на текущий позиции — 
, а таблица выдаёт переход 
, то это означает, что на текущем шаге происходит следующее:
Символ
в текущей позиции заменяется на символ 
.Двигаемся влево если
, вправо, если 
, или завершаем программу, если 
.Меняем состояние на
.
Программа на повестке
Итак, мы хотим понять, что делает следующая программа:
Алфавит состоит из трёх символов A, B, C + пустой.
Всего пять состояний q0, q1, q2, q3, q4.
Таблица переходов выглядит так
Q\E | A | B | C | λ |
q0 | B R q2 | C R q3 | A R q1 | |
q1 | A R q1 | C L q4 | B L q4 | ! |
q2 | C L q4 | B R q2 | A L q4 | ! |
q3 | B L q4 | A L q4 | C R q3 | ! |
q4 | A L q4 | B L q4 | C L q4 | λ R q0 |
Один переход не указан: по задумке таких переходов происходить не должно. Эту программу предполагается применять к последовательности одинаковых символов. Можете проверить, такая программа делает из одной последовательности одинаковых символов другую последовательность. Вроде бы ничего интересного, можно было бы обойтись и одним состоянием, но давайте не торопиться с выводами.
Попробуем проанализировать …
Давайте посмотрим, что происходит в каждом из состояний:
q0 всегда делает замену символа (A→B, B→C, C→A) и переводит программу в одно из состояний q1, q2, q3.
q1, q2, q3 устроены схожим образом: q1 едет вправо по символу А, а на B или С останавливается меняя один на другой и переводя программу в состояний q4. q2, q3 действуют по аналогии с q1, но с буквами.
q4 едет в начало ленты и переводит систему в состояний q0.
Программа останавливается, если q1, q2 или q3 доехали до конца ленты по своему символу, т. е. в случае если все символы одинаковы после замены в состоянии q0.
Итого программу можно представить в виде цикла, каждая итерация которого делает что-то такое:
Меняем первый символ на ленте: A становится B, B становится С, а С становится А.
Ищем самый левый символ отличный от того, что мы только что записали в первой позиции и меняем его на оставшийся символ, т.е. если в первую позицию мы записали В, то дальше мы ищем первую А или С и меняем А на С или С на А.
Так, давайте ка напишем это на языке попроще и посмотрим, что происходит
def misterious_ABC_sequence(length: int):
sequence = ['A' for _ in range(length)]
first_symbol_map = {'A': 'B', 'B': 'C', 'C': 'A'}
changes = []
states = []
while True:
new_symbol = first_symbol_map[sequence[0]]
changes.append(f"{0}: {sequence[0]} -> {new_symbol}")
sequence[0] = new_symbol
states.append([x for x in sequence])
was_changed = False;
for i in range(1, length):
if sequence[i] != sequence[0]:
new_symbol = ({'A', 'B', 'C'} - {sequence[0], sequence[i]}).pop()
changes.append(f"{i}: {sequence[i]} -> {new_symbol}")
sequence[i] = new_symbol
states.append([x for x in sequence])
was_changed = True
break
if not was_changed:
return changes, statesДавайте попробуем позапускать. Первое, что можно обнаружить — это то, что длина states — это степ 
, где 
— длина последовательности. Хммм, давайте посмотрим чуть внимательней на changes при запуске с length=5.
0: A -> B
1: A -> C
0: B -> C
2: A -> B
0: C -> A
1: C -> B
0: A -> B
3: A -> C
0: B -> C
1: B -> A
0: C -> A
2: B -> C
0: A -> B
1: A -> C
0: B -> C
4: A -> B
0: C -> A
1: C -> B
0: A -> B
2: C -> A
0: B -> C
1: B -> A
0: C -> A
3: C -> B
0: A -> B
1: A -> C
0: B -> C
2: A -> B
0: C -> A
1: C -> B
0: A -> BNota bene! spoilers ahead. Если вы хотите сами подумать над задачей, то стоит на этом месте остановится, очень скоро будут спойлеры!
Так, что еще можно вынести, ну например можно обратить внимание, что 0-ая ячейка меняется на каждом втором шаге, 1-ая на каждом 4-ом шаге, 2-ая на каждом 8-ом и так далее. Хмм, может это как-то связано с двоичной системой счисления? Непонятно, вроде бы состояний ленты 
, так как на каждой из k позиций может быть написан один из трех символов. Давайте посмотрим, что происходит на ленте на итерациях, соответствующих степеням двойки
0 ['A', 'A', 'A', 'A', 'A']
1 ['B', 'A', 'A', 'A', 'A']
3 ['C', 'C', 'A', 'A', 'A']
7 ['B', 'B', 'B', 'A', 'A']
15 ['C', 'C', 'C', 'C', 'A']
31 ['B', 'B', 'B', 'B', 'B']Ага, значит за 
шагов мы меняем первые 
символов на B или C (если начинали с последовательности из символов А).
Раскрываем карты
Ладно, если вы еще не догадались, то это программа решает
Задачу …
о Ханойских башнях
Суть задачи заключается в следующем: у вас есть 
дисков разного диаметра с дырками посередине и три вертикальных стержня, на которые эти диски можно расположить. Изначально диски расположены на одном из стержней в порядке уменьшения диаметра, за один ход разрешается переместить верхний диск на другой стержень, если там уже не лежит диск меньшего диаметра. Нужно перенести все диски с одного стержня на другой. Дополнительный вопрос — какое минимальное количество ходов для этого нужно.
Традиционно это задача является хорошим примером рекурсивных функций и соответствующего индуктивного мышления: давайте представим, что мы научились перекладывать башню размером 
c одного стержня на другой, тогда, чтобы переложить башню размером 
, можно сначала перенести верхние 
дисков на другой стержень, переложить самый нижний диск и снова перенести верхние 
дисков поверх переложенного нижнего стержня.
Если обозначить за 
количество действий в таком алгоритме, то получается, что
Очевидно, что 
, и соответственно это рекуррентное соотношение приводит к явной формуле
Легко увидеть, что это также является и оптимальным алгоритмом с точки зрения количества ходов: в какой-то момент нам так или иначе придётся переложить самый нижний диск, а это возможно сделать только если все остальные диски сложены на одном из стержней. А вот и соответствующая рекурсивная программа:
def hanoi_towers_recursive(length: int, source: int, target: int):
if length == 1:
return [(0, source, target)]
intermediate = 3 - source - target
return [*hanoi_towers_recursive(length - 1, source, intermediate),
(length - 1, source, target),
*hanoi_towers_recursive(length - 1, intermediate, target)]И вывод следующего кода идентичен листингу выше для длины 5
towers = ['A', 'B', 'C']
for i, (disk, source, target) in enumerate(hanoi_towers_recursive(5, 0, 1)):
print(f"{i + 1} {disk}: {towers[source]} -> {towers[target]}")Рекурсия в этом случае выступает мощным инструментом, благодаря которому довольно сложную на первый взгляд задачу получается решить очень простым и понятным методом.
Почему рекурсия и МТ выдают одинаковый результат?
Программа МТ для решения ханойской башни выстроена не из соображений рекурсии, а как обычный итеративный алгоритм, который имитирует поведение рекурсивного алгоритма. Чтобы понять почему они делают одно и тоже давайте немного посмотрим на сам алгоритм и на пару его свойств. Начнем с ленточного представления состояния дисков на стержнях. В МТ мы считаем диски пронумерованными, на ленте зарезервировано k ячеек для каждого из дисков, символ означает на каком из стержней A, В или С расположен конкретный диск. Так как на каждом стержне диски располагаются в порядке убывания диаметра, то расположение дисков однозначно задаётся стержнем. Дальше заметим следующее
Наблюдение №1. В любой момент времени можно либо переместить самый маленький диск двумя способами, либо какой-то другой одним способом кроме случая когда все диски на одном стержне.
Здесь все довольно просто. Самый маленький диск обязан быть на самом верху и его можно перенести на любой из соседних стержней. Если же не все стержни находятся на одном, то возможен еще один ход: меньший из дисков (кроме самого маленького) можно перенести на стержень, где не расположен самый маленький диск.
Наблюдение №2. Каждый нечетный ход оптимального алгоритма делается самым маленьким диском.
Это можно видеть и из структуры рекурсивного алгоритма, но можно и заключить из предыдущего наблюдения: если мы попытаемся два раза подряд сделать ход не наименьшим диском, то получится только вернуться к предыдущему состоянию. Отсюда получается, что в оптимальном алгоритме ходы меньшего диска и всех остальных должны чередоваться
Наблюдение №3. Маленький диск перемещается либо по направлению A→B→C→A, либо A→C→B→A на протяжении всего алгоритма.
Вот это уже менее очевидное свойство, его легко увидеть, но сложнее доказать почему так происходит. Если быть точнее, то происходит вот что
Лемма. Оптимальный алгоритм, перемещающий башню длины k со стержня А на стержень В делает
Первый и последний ход A→B самым маленьким диском при нечетных k
Делает первый ход А→C и последний C→B самым маленьким диском для четных k
Лемма доказывается по индукции. Алгоритм должен сначала перенести верхние 
дисков A→C, перенести нижний диск на В и перенести 
дисков C→B. Если 
нечетно, а значит первый ход делается A→C (первый ход переноса A→C), а последний C→B (последний ход переноса С→B). Для четного же 
первый и последний ходы становятся A→В.
Из леммы легко обосновывается Наблюдение №3: опять же воспользуемся индукцией для четных k получаем, что первый перенос 
верхних дисков проходил в направлении A→С→В→A, последним ходом был А→С, следующим ходом после перемещения нижнего диска будет С→B и дальше движение в том же направлении. Для нечетного k последний ход переноса верхних 
дисков заканчивается на A→B, а второй перенос начинается с В→C и движение происходит в направлении A→B→C→A.
Так, мы разобрались с тем, что состояние q0 в МТ программе отвечает за перегон наименьшего диска по кругу и это соответствует поведению оптимального алгоритма. Наконец из наблюдения №1 заключаем, что ход не самым маленьким диском единственен: если на предыдущем шаге мы переместили самый маленький диск на стержень X, то следующим ходом мы обязаны перенести наименьший диск, не лежащий на Х, на оставшийся стержень. Эта логика в точности описана в состояниях q1, q2, q3 и её аналогу misterious_ABC_sequence.
Хмм, а можно ли еще уменьшить программу?
Как оказывается можно, но есть нюанс: возможно сделать программу на МТ в 4 состояния, которая решает задачу о хайноских башнях, но не за минимальное возможное число перекладываний. Спросим себя, на чем мы можем сэкономить. В варианте с пятью состояниями преобразование первого символа происходит по кругу «A → B → C → A → B → C …». А что если исключить в этой последовательности вовсе символ «C»? В интерпретации Ханойской башни это означало бы, что первый диск никогда не побывает на стержне «C»! Будет ли это препятствием для решения классической Ханойской башни? Нет! Предлагаю читателям самостоятельно доказать это несложное утверждение.
Однако, вернемся к нашей МТ. Ранее после выполнения хода первым диском мы запоминали посредством состояния, куда был перемещен первый диск:
Если первый диск переместился со стержня «A» на стержень «B», то МТ переходила в состояние q2;
Если первый диск переместился со стержня «B» на стержень «C», то МТ переходила в состояние q3;
Если первый диск переместился со стержня «C» на стержень «A», то МТ переходила в состояние q1.
Теперь, когда первому диску запрещено перемещаться на стержень «C», надобность в состоянии q3 исчезает! Как и ранее, ход не первым диском возможен всегда единственным образом. Поэтому после выполнения хода первым диском, мы спускаемся по списку дисков, пропуская символы, совпадающие с нынешним расположением первого диска. Далее возможны два варианта: либо мы выходим на пустую ячейку ленты (и тогда достигнуто заключительное состояние), либо находим иной символ и делаем единственно возможный ход. В итоге получается следующая МТ с четырьмя состояниями.
Q\E | A | B | C | λ |
q0 | B R q2 | A R q | ||
q1 | A R q1 | C L q3 | B L q3 | ! |
q2 | C L q3 | B R q2 | A L q3 | ! |
q3 | A L q3 | B L q3 | C L q3 | λ R q0 |
Эта МТ успешно справляется с поставленной задачей и, моделируя ходы Ханойской башни, преобразует строку из символов «A» независимо от четности всегда в строку из символов «B». Правда, расплатой за меньшее число состояний будет большее число ходов.
Быть может что-то еще?
Казалось бы, можно остановиться, но мы поразмышляем над задачей еще: что если изначально диски размещены не на одном стержни, а как-то произвольно? Окончанием игры будет служить башня, собранная по стандартным правилам на одном из стержней. В такой постановке задача всегда имеет решение. Заметим, что фраза «произвольное начальное размещение дисков» имеет два принципиально различных толкования: либо диски изначально размещены по стержням произвольным образом без нарушения правила «диск большего диаметра не может лежать на диске меньшего диаметра», либо при выборе начальной конфигурации упомянутое выше правило не проверяется. При любом толковании задача всегда имеет решение. Далее мы остановимся на первом толковании перемешанной Ханойской башни по той причине, что выбранный способ представления данных на ленте МТ, когда дискам, начиная с первого, соответствуют символы стержней, не позволяет реализовать второе толкование. И вот сейчас «изюминка на торте» – при незначительной переделке МТ с четырьмя состояниями оказывается способной решать перемешанную Ханойскую башню! Изменения управляющей таблицы связаны с возможным начальным размещением первого диска на стержне «C». Ниже приводится окончательный вариант МТ с четырьмя состояниями.
Q\E | A | B | C | λ |
q0 | B R q2 | A R q | B R q2 | |
q1 | A R q1 | C L q3 | B L q3 | ! |
q2 | C L q3 | B R q2 | A L q3 | ! |
q3 | A L q3 | B L q3 | C L q3 | λ R q0 |
Ссылки
Басов И Решение задачи о ханойских башнях на машине Тьюринга
Пинаев В. Н. Ханойские перемешанные башни: - Информатика и образование.- 1992.- №3-4.- с.97-98
Дональд Кнут Программирование как искусство // речь на присуждении премии Тьюринга http://rkka21.ru/docs/turing-award/dk1974r.pdf
Друзья и коллеги! С удовольствием хотел бы прорекламировать CS Space — открытый научный клуб по CS-related темам; идейных последователей питерского Computer Science Club (и CS Center), расформировавшегося после известных событий. Ребята организуют крутые лекции и курсы по CS от профессионалов своего дела, да еще и помогают мне с написанием научно-популярных статей!
Сайт сообщества: csspace.io
Telegram-канал: t.me/csspace
Если вам понравилась статья — поставьте плюс, автору всегда приятно когда его работу ценят. Возможно вас также заинтересует мой канал А зачем это нужно? где я рассказываю о том, что математику и алгоритмы придумали не только для собеседований в бигтехи.
