Все, что разработчику нужно знать про машины Тьюринга, — простым языком

Разработчик программного обеспечения Валерий Жила объяснил, как устроены машины Тьюринга. По его словам, когда он начинал разбираться с этой концепцией, у него разболелась голова. Теперь же специалист считает, что в ней нет ничего сложного. Что это за машины и зачем они нужны, разработчик максимально просто объяснил в треде. 

Примечание: машина Тьюринга (МТ) — это абстракция из мира Computer Science, которой не существует в физическом мире. 

Обычная машина Тьюринга состоит из трех частей, из которых первые две технические, а в третьей, по словам Валерия, происходит магия. Они называются: 

• головка чтения и записи (далее «указатель»);
• бесконечная лента с ячейками;
• программа машины.

Указатель

Указатель обозначается стрелкой, как показано на рисунке ниже, и всегда указывает на одну ячейку. Этот элемент может следующее: 

• считывать содержимое ячейки;
• записать что-то в нее;
• перемещаться.

Пример: указатель стоит на ячейке, в которой содержится число «два». В таком положении он может прочитать ее содержимое, перезаписать или поменять свое положение.

Указатель может двигаться тремя способами:

• на одну ячейку влево;
• на одну ячейку вправо;
• стоять на месте.

Запишем в ячейку ноль и переместим указатель на одну ячейку влево. Вот что получится:

Все действия машин строятся следующим образом: 

• читаем ячейку;
• что-то пишем в ней — в зависимости от программы или прочитанного;
• перемещаемся.

Вышеописанное действие можно описать как (2,0,L), то есть: читаем два, пишем ноль, едем влево. 

Движение часто обозначают так: 

• L (Left) — едем влево;
• N (None) — стоим на месте;
• R (Right) — едем вправо.

Бесконечная лента

В примере выше была лента из трех ячеек. Этого мало. Давайте рассмотрим из семи. Автор пронумеровал их от -3 до 3.

Примем за правило, что при запуске машины указатель всегда находится над ячейкой под номером 0.

Примечание: указанные номера изображены только для наглядности, в настоящей МТ их нет, и она не может «прыгнуть» на ячейку с конкретным номером. У машин Тьюринга нет Random Access. 

По умолчанию ячейки заполнены «пустыми символами». Это делают для того, чтобы при прочтении можно было проверить, пусто ли поле. Пустые символы обозначают простыми пустыми ячейками или символом space. 

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

В основном машины Тьюринга бывают двух видов: 

• Которые начинают с входными данными на ленте и должны как-то преобразовать данные — это МТ, которые считают. Умножают, делят, сортируют массивы и так далее. «Считают» — в общем смысле слова, то есть оставляют результат на ленте и останавливаются.
• Которые начинают с входными данными на ленте и используют их для того, чтобы дать ответ «ДА/НЕТ». Истинно ли выражение? Четно ли число? Отсортирован ли массив? Связан ли граф? Эти машины Тьюринга «решают» и останавливаются в состоянии TRUE или FALSE.

По словам Валерия, МТ второго типа намного важнее, сложнее и интереснее первого для Computer Science. 

На ленте могут стоять только заранее определенные символы, и они не могут добавляться по ходу работы машины. Для большинства задач с входными данными, закодированными двоичным кодом, удобно пользоваться тремя символами 1,0 и # для разграничения. Плюс «пустой» символ. 

Вводные данные машины, например, число, для которого нужно проверить, является ли оно простым, стоят перед запуском машины в выбранной кодировке на ленте, справа от указателя. Например, вот так бы выглядело число 9 (=1001 в двоичной системе) в качестве вводных данных: 

Программа машины

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

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

Пример: возьмем программу, которая отзеркаливает последовательность 0 и 1, стоящую на ленте, то есть делает String.reverse. Например, 01011 будет трансформировано в 11010. 

Примечание: программы ТМ зачастую большие и сложные, делают кучу странной мишуры, постоянно ездят из конца слова в другой конец. Это вытекает из максимальной простоты инструментов ТМ. Программа машины Тьюринга может выполнить любую алгоритмически решаемую задачу, но на это будет затрачено огромное количество времени. 

Ниже показано, как будет выглядеть программа МТ, которая будет переворачивать строку. Автор предпочел не разбирать ее подробно, потому что даже такая простая задача может занять ни один час. 

 Принцип работы программы: 

• указатель едет к слову;
• пишет перед ним # — разграничитель;
• «отщипывает» самую левую букву от слова, заменяя ее на # и запоминая букву;
• катится влево и пишется эту букву за #.

 И так по одной букве, катаясь туда-сюда, МТ отзеркалит заданное слово. Когда оно закончится, останется только стереть все # с лент и закончить работу. 

Ниже приведен пример работы этой программы для слова 10, состоящего из двух букв: 

Выводы

• Обычно создавать автоматы для доказательств не нужно. Это слишком сложно для человека, у МТ для поиска корней квадратного уравнения может быть более 100 состояний в программе.
• Обычно описание машины Тьюринга делается в текстовом виде, ближе к обычной программе. Например: едем к слову, вырезаем букву и пишем ее левее самого левого элемента на ленте, едем назад, продолжаем, пока правое слово не кончится. При правильной структуре таких текстовых описаний можно приноровиться быстро считать их алгоритмическую сложность по времени и памяти.
• Машина машине рознь. Есть модификации с лентами шириной не в 1, а в несколько ячеек В таких МТ считываться будет сразу целое окно ячеек (вектор):

• Еще одна модификация, где в рамках одной машины используется несколько лент и несколько указателей:

• Плюс модификаций в том, что их все можно симулировать на обычной МТ, с одной лентой и с одним указателем — значит, что и решают они ровно те же задачи, а значит, что обычная машина Тьюринга может не меньше, чем  машина с тысячей лент и указателей. А это значит, что можно решать задачи на модификациях МТ, что в разы удобнее, и писать, например, что доказано, что какую-либо машину Тьюринга можно симулировать на обычной машине.
• МТ не всегда останавливаются, и точно так же, как обычные программы, могут попасть в бесконечный цикл. Это служит почвой для десятков парадоксов, вроде «проблемы остановки», которые широко используются в теории вычислимости.
• Если в основе программы МТ лежит детерминистичный конечный автомат (один переход в другое состояние для каждого символа из каждого состояния), то и сама машина Тьюринга будет являться детерминистичной. Сокращенно— ДТМ. Если автомат недетерминистичный, то, соответственно, такой будет и МТ. Сокращенно — НДТМ.

Вот и все!