Пролог.
Казалось бы, какое отношение к высшей математике может иметь абстрактная машина, формально пошагово выполняющая заданные инструкции? На самом деле Машина Тьюринга - это мощный математический инструмент, который используется не только для наглядной интерпретации понятия алгоритма, но также является хорошим средством для простого доказательства некоторых теорем, которые будут рассмотрены далее в этой и других статьях.

Предполагается, что читатель знаком с понятием алгоритма.

Теоретический минимум.
Машина Тьюринга - абстрактная (воображаемая) "вычислительная машина" некоторого точно охарактеризованного типа, дающая пригодное для целей математического рассмотрения уточнение общего интуитивного представления об алгоритме.

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

Пример того, как это могло бы выглядеть представлен на следующих рисунках:



Лента. Каждая ячейка ленты может находиться в одном из множества состояний, которые, для удобства, помечаются символами . Назовем эти символы - символами внешнего алфавита машины, при этом сама лента часто называется внешней памятью. Если ячейка пустая, то такую ячейку будем обозначать символом . Без ограничения общности ленту можно считать бесконечной лишь с одной стороны. В этом случае, для удобства, введем специальный символ , обозначающий начало ленты. Этот символ имеет строго определенное место, его нельзя ни стирать, ни сдвигать. Тогда ленту можно считать однонаправленной (бесконечной вправо) и ее ячейки удобно просматривать слева направо.

Внутренняя память.
Предполагается, что число возможных состояний внутренней памяти конечное и для каждой машины фиксированное. Состояние внутренней памяти мы будем обозначать символами или любыми другими символами, не входящими во внешний алфавит машины. Совокупность символов, обозначающих состояния внутренней памяти, называется внутренним алфавитом машины или внутренними состояниями машины. Одно из этих состояний называется начальным, с него начинает работу любая машина, пусть это будет состояние . В процессе работы машина может какое-то количество шагов оставаться в состоянии или возвращаться в него позднее. Еще одно специальное состояние - заключительное. Символ, обозначающий заключительное состояние, будет называться стоп - символом. Роль стоп - символа далее будет играть символ . Если в какой-то момент времени внутренняя память машины приходит в заключительное состояние , то дальнейших изменений в машине не происходит и машина называется остановившейся. Может случиться, что в машине никогда не будет происходить никаких изменений и при каком-то другом внутреннем состоянии . Однако в этом случае мы будем говорить, что машина продолжает работать «вечно». В большинстве случаев не останавливающиеся машины не имеют никакой ценности, так как невозможно запротоколировать факт окончания выполнения алгоритма и, соответственно, считать полученный ответ. Обычно говорят, что, если машина не останавливается на входном слове , то она к этому слову неприменима.

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

Работа машины состоит в том, что она из данного «состояния» по истечении одного такта работы механического устройства переходит в следующее «состояние», затем из этого состояния по истечении такта работы переходит в новое состояние и так далее. Т.о. если машина, имея внутреннее состояние и воспринимая ячейку ленты с символом , изменяет свое внутреннее состояние на и одновременно содержимое воспринимаемой ячейки заменяет символом , а управляющая головка сдвинется на одну ячейку вправо ®, то говорят, что машина выполняет команду соответственно . Если управляющая головка сдвинется влево (L) или останется неподвижной (Н), то команды записываются соответственно:



Программа машины Тьюринга - это совокупность команд установленного формата.

Так как работа машины по условию целиком определяется состоянием в данный момент ее внутренней памяти и содержимым воспринимаемой ячейки , то для каждых , программа машины должна содержать одну и только одну команду, начинающуюся словом . Таким образом, программа машины с символами и состояниями содержит максимум команд. При этом некоторые команды являются «мертвыми», в том случае, если ни при каких входных словах в данном алфавите невозможно наступление этой конфигурации. В грамотной, с точки зрения реализации, программе таких строк быть не должно, хотя формально их наличие ошибкой не является.

Важный тезис, который нам может пригодиться в этой и других статьях:

Примеры.
Пример 1. Алфавит . Заменить во входном слове все символы на .
Решение (с пояснениями).
- символ начала ленты, сдвигаемся вправо без изменения состояния.
- если символ "1", то ничего не меняем и двигаемся дальше.
- если символ "0", то меняем его на "1" и двигаемся дальше.
- если наткнулись на пустую ячейку, то останавливаемся и завершаем работу.

Пример 2. Алфавит . Перезаписать входную ленту зеркальным отражением входной строки (например .
Решение. Можно было попробовать решить задачу в лоб, но намного проще будет добавить вспомогательные символы, которые впоследствии можно убрать. В нашем случае, добавим и





_________________________




_________________________





_________________________





_________________________



_________________________



_________________________





_________________________





_________________________



________________________



________________________



________________________




Посмотрели, ужаснулись, а теперь давайте разбираться. Суть решения заключается в том, чтобы гонять нашу машину с одного конца в другой, при этом "запоминая" символ с одного конца и записывая его в другой конец, постепенно "сужая" расстояния между символами. Так в начале "границами" обрабатываемой строки были и , а затем помеченные * символы. Построчно программу разбирать не будем - ограничимся объяснениями каждого состояния машины:
- инициализирующее состояние и заодно в этом состоянии машина доходит до пустой ячейки ленты
- в этом состоянии машина, можно сказать "копирует" символ ячейки. Как это происходит - поймем из анализа следующих состояний.
и - в этих состояниях машина идет до начала ленты или до первого помеченного символа. Причем в состоянии машина "держит в памяти" символ , а -
и - в этих состояниях машина записывает в ячейку "скопированное значение", а также "копирует" символ из этой ячейки
и - аналогичны состояниям и , только при этом машина двигается в другую сторону.
и - аналогичны состояниям и , с тем отличием, что включают состояние , чтобы начать новый цикл обработки строки.
Состояния , , , и имеют "выход" в состояние из образовавшегося цикла в случае, если машина пометила все символы.
- вспомогательное состояние, возвращающее головку машины на начало ленты.
- в этом состоянии машина снимает ранее поставленные метки.
Как видите, все довольно просто. Предлагаю читателям самостоятельно на листочке или на компьютере в блокноте проверить работоспособность программы. Если программа оказалась неработоспособна, то, пожалуйста, напишите в этой теме контрпример - вероятно я опечатался, когда перепечатывал со своего листочка решение или (всякое бывает) при написании программы.
В качестве самостоятельного задания, предлагаю читателям придумать альтернативный алгоритм для решения этой задачи, а лучше более оптимальный. Оптимальным будем считать тот, в котором вам удастся довольно сильно сократить количество команд в программе или сократить количество используемых состояний машины (хотя бы на 3).

Еще одно самостоятельное задание (решение которого я выложу через две недели). Алфавит унарный (т.е. состоит из одного символа, например "|"). Преобразуйте с помощью машины Тьюринга входное унарное число в двоичное. Пример: .

Все решения и замечания можно выложить в этой теме или мне в личные сообщения :agree:

Задачи об остановке разных машин на разных лентах даёшь!

BA3a, ок, будет

Добавил новый пример и задание для самостоятельного решения

Поправил пример перевода унарных чисел в двоичные. Обратите внимание, что !

Как-то пассивненько. Может еще один-два примера разобрать?

Silver MC's, ну могу я поразгадывать, но это же нечестно будет. А в целом — если б не курс Вольфенгагена, этот курс был бы моим любимым за всё время обучения.

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

Кстати, может никто не выкладывает, потому что даже идей как решать нету? Задавайте тогда вопросы, высказывайте свои мысли по поводу решения - это тоже ведь очень важно и интересно будем смотреть, рассуждать, спорить B)