Машина тьюринга удвоение числа
Машина Тьюринга
Машина Тьюринга представляет собой (абстрактное) устройство, состоящее из ленты, управляющего устройства и считывающей головки.
Лента разбита на ячейки. Во всякой ячейке в точности один символ из внешнего алфавита A=
Считывающая головка перемещается вдоль ленты так, что в каждый момент времени она обозревает ровно одну ячейку ленты. Головка может считывать содержимое обозреваемой ячейки и записывать в нее вместо обозреваемого символа некоторый новый символ из внешнего алфавита A (возможно тот же самый).
В процессе работы управляющее устройство в зависимости от состояния, в котором оно находится и символа, обозреваемого головкой, изменяет свое внутреннее состояние q. Затем выдает головке приказ напечатать в обозреваемой ячейке определенный символ из внешнего алфавита A, а потом приказывает головке либо остаться на месте, либо сдвинуться на одну ячейку вправо, либо сдвинуться на одну ячейку влево. Попав в заключительное состояние, машина прекращает работу.
Конфигурацией на ленте (или машинным словом) называется совокупность, образованная:
2) состоянием внутренней памяти qr
3) номером k воспринимаемой ячейки
Конфигурацию машины будем записывать так:
здесь r-воспринимаемая ячейка, выделяется в виде дроби.
Если в программе машины для пары (qi,au) пятерка отсутствует, то в таблице на пересечении строки au, и столбца qi ставится прочерк.
Если машина, начав работу с некоторым словом P, записанным на ленте, придет в заключительное состояние, то она называется применимой к этому слову. Результатом ее работы считается слово, записанное на ленте в заключительном состоянии. В противном случае, машина называется не применимой к слову Р.
Пример. Построим машину Тьюринга, складывающую натуральные числа, записанные в унарной системе счисления (т.е. записанные при помощи одного символа |. Например 5=|||||.).
Решение. Рассмотрим алфавит А = <|, +, Λ>.
Машина определяется следующей программой:
Выпишем последовательно возникающие при работе этой машины конфигурации на исходном слове ||+|||, т.е. 2+3. Здесь при записи конфигурации будем использовать следующее соглашение: состояние, в котором находится машина, записывается в круглых скобках справа за обозреваемой буквой.
Пример. Построить машину Тьюринга, удваивающую натуральные числа, записанные в унарной системе счисления.
Решение. Искомую машину построим в алфавите A=<|, α, Λ>.
Программа такой машины может выглядеть так:
Применим полученную машину к слову ||.
Введение новой буквы α и замена исходных | на α позволяет различить исходные | и новые (приписанные) |. Состояние q1 обеспечивает замену | на α, состояние q2 обеспечивает поиск α, предназначенных для замены на |, и останов машины в случае, когда α не обнаружено, q3 обеспечивает дописывание | в случае, когда произошла замена α на |.
Навигация
Календарь
Машина Тьюринга. Задачи и решения
Один из важнейших вопросов современной информатики — существует ли формальный исполнитель, с помощью которого можно имитировать любого формального исполнителя. ответ на этот вопрос был получен почти одновременно двумя выдающимися учеными — А. Тьюрингом и Э. Постом. Предложенные ими исполнители отличались друг от друга, но оказалось, что они могут имитировать друг друга, а главное — имитировать работу любого формального исполнителя.
Что такое формальный исполнитель? Что значит — один формальный исполнитель имитирует работу другого формального исполнителя? Если Вы играли в компьютерные игры — на экране объекты беспрекословно подчиняются командам играющего. Каждый объект обладает набором допустимых команд. В то же время компьютер сам является исполнителем, причем не виртуальным, а реальным. Вот и получается, что один формальный исполнитель имитирует работу другого формального исполнителя.
Рассмотрим работу Машины Тьюринга.
Машина Тьюринга представляет собой бесконечную ленту, поделенную на ячейки, и каретку (считывающе-печатающее устройство), которая движется вдоль ленты.
Таким образом Машина Тьюринга формально описывается набором двух алфавитов:
A=
Q=
Каждая ячейка ленты может содержать символ из внешнего алфавита A =
Допустимые действия Машины Тьюринга таковы:
1) записать какой-либо символ внешнего алфавита в ячейку ленты (символ, бывший там до того, затирается)
2) сместиться в соседнюю ячейку
3) сменить состояние на одно из обозначенных символом внутреннего алфавита Q
Машина Тьюринга — это автомат, который управляется таблицей.
Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q =
В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей
· символ из алфавита A
· направление перемещения: «>» (вправо), «
Машина Тьюринга
Содержание
Машина Тьюринга (англ. Turing machine) — модель абстрактного вычислителя, предложенная британским математиком Аланом Тьюрингом в 1936 году. Эта модель позволила Тьюрингу доказать два утверждения. Первое — проблема останова неразрешима, т.е. не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте зациклится или прекратит работу. Второе — не существует такой машины Тьюринга, которая способна определить, что другая произвольная машина Тьюринга на её ленте когда-нибудь напечатает заданный символ. В этом же году был высказан тезис Чёрча-Тьюринга, который терминах теории рекурсии формулируется как точное описание интуитивного понятия вычислимости классом общерекурсивных функций. В этой формулировке часто упоминается как просто тезис Чёрча. В терминах вычислимости по Тьюрингу тезис гласит, что для любой алгоритмически вычислимой функции существует вычисляющая её значения машина Тьюринга. В виду того, что классы частично вычислимых по Тьюрингу и частично рекурсивных функций совпадают, утверждение объединяют в единый тезис Чёрча — Тьюринга.
Неформально машина Тьюринга определяется как устройство, состоящее из двух частей:
При запуске машины Тьюринга на ленте написано входное слово, причём на первом символе этого слова находится головка, а слева и справа от него записаны пустые символы. Каждый шаг головка может перезаписать символ под лентой и сместиться на одну ячейку, если автомат приходит в допускающее или отвергающее состояние, то работа машины Тьюринга завершается.
Определение [ править ]
Определение машины [ править ]
Отметим, что существуют различные вариации данного выше определения (например, без отвергающего состояния или с множеством допускающих состояний), которые не влияют на вычислительные способности машины Тьюринга.
Определение процесса работы [ править ]
Особо следует рассмотреть случай переходов по пробельному символу:
Для машины Тьюринга, которая пишет символ [math]B[/math] на ленту также можно дать аналогичное формальное определение. Оно будет отличаться тем, что символы в строчках конфигурации могут содержать пробелы, и для того, чтобы эти строчки имекли конечную длину, нужно аккуратно учесть наличие пробелов при записи правил перехода.
Результат работы [ править ]
Примеры машин-распознавателей и машин-преобразователей будут даны ниже.
Примеры машин Тьюринга [ править ]
Прибавление единицы [ править ]
Для начала приведём пример машины-преобразователя, которая прибавляет единицу к числу, записанному на ленте в двоичной записи от младшего бита к старшему. Алгоритм следующий:
| [math]0[/math] | [math]1[/math] | [math]B[/math] | |
| [math]S[/math] | [math]\langle R, 1, \downarrow \rangle[/math] | [math]\langle S, 0, \rightarrow \rangle[/math] | [math]\langle R, B, \leftarrow \rangle[/math] |
| [math]R[/math] | [math]\langle R, 0, \leftarrow \rangle[/math] | [math]\langle R, 1, \leftarrow \rangle[/math] | [math]\langle Y, B, \rightarrow \rangle[/math] |
Проверка того, является ли слово палиндромом [ править ]
| [math]0[/math] | [math]1[/math] | [math]B[/math] | |
| [math]S[/math] | [math]\langle F_0, B, \rightarrow \rangle[/math] | [math]\langle F_1, B, \rightarrow \rangle[/math] | [math]\langle Y, B, \downarrow \rangle[/math] |
| [math]F_0[/math] | [math]\langle F_0, 0, \rightarrow \rangle[/math] | [math]\langle F_0, 1, \rightarrow \rangle[/math] | [math]\langle B_0, B, \leftarrow \rangle[/math] |
| [math]F_1[/math] | [math]\langle F_1, 0, \rightarrow \rangle[/math] | [math]\langle F_1, 1, \rightarrow \rangle[/math] | [math]\langle B_1, B, \leftarrow \rangle[/math] |
| [math]B_0[/math] | [math]\langle R, B, \leftarrow \rangle[/math] | [math]\langle N, 1, \downarrow \rangle[/math] | [math]\langle Y, B, \downarrow \rangle[/math] |
| [math]B_1[/math] | [math]\langle N, 0, \downarrow \rangle[/math] | [math]\langle R, B, \leftarrow \rangle[/math] | [math]\langle Y, B, \downarrow \rangle[/math] |
| [math]R[/math] | [math]\langle R, 0, \leftarrow \rangle[/math] | [math]\langle R, 1, \leftarrow \rangle[/math] | [math]\langle S, B, \rightarrow \rangle[/math] |
Варианты машины Тьюринга [ править ]
В этом разделе приведены различные варианты машин Тьюринга, которые не отличаются от обычных машин Тьюринга по вычислительной мощности.
Многодорожечная машина Тьюринга [ править ]
Машина Тьюринга с полубесконечной лентой [ править ]
Заменив у машины Тьюринга бесконечную в обе стороны ленту на бесконечную в одну сторону, мы не теряем в вычислительной мощности. По произвольной машине Тьюринга строится двухдорожечная машина с полубесконечной лентой.
Существует алгоритм, по которому для любой машины Тьюринга может быть построена эквивалентная машина Тьюринга с объявленным свойством. Сначала занумеруем ячейки рабочей ленты машины Тьюринга с бесконечной лентой следующим образом:
Затем перенумеруем ячейки, и запишем символ [math]c \in \Pi \setminus \Sigma, B[/math] в начало ленты, который будет означать границу рабочей зоны:
Начальное состояние новой машины Тьюринга устанавливается в одной или другой зоне в зависимости от того, в какой части исходной ленты располагалась головка считывания-записи в исходной конфигурации.
Многоленточная машина Тьюринга [ править ]
Многоленточная машина с [math]n[/math] дорожками эмулируется многодорожечной машиной с [math]2n[/math] дорожками следующим образом: каждая нечётная дорожка соответствует ленте исходной машины, а на каждой чётной дорожке отмечены специальным символом [math]*[/math] позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).
Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов [math]*[/math] символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.
Аланом Тьюрингом было сформулировано следующее утверждение:
; n ³ 1. Постройте машину Тьюринга с внешним алфавитом А = <а0, 1>, которая отыскивала бы левую единицу этого слова (т. е. приходила бы в состояние, при котором обозревалась бы ячейка с самой левой единицей данного слова, и в этом положении останавливалась), если в начальный момент головка машины обозревает одну из ячеек с буквой данного слова.
