Машина тьюринга удвоение числа

Машина Тьюринга

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

Лента разбита на ячейки. Во всякой ячейке в точности один символ из внешнего алфавита A=0,a₁. a_n>. Некоторый символ (будем обозначать его Λ) алфавита A называется пустым, а любая ячейка, содержащая в данный момент пустой символ, называется пустой ячейкой (в этот момент). Лента предполагается потенциально неограниченной в обе стороны.

Считывающая головка перемещается вдоль ленты так, что в каждый момент времени она обозревает ровно одну ячейку ленты. Головка может считывать содержимое обозреваемой ячейки и записывать в нее вместо обозреваемого символа некоторый новый символ из внешнего алфавита A (возможно тот же самый).

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

Конфигурацией на ленте (или машинным словом) называется совокупность, образованная:

2) состоянием внутренней памяти q_r

3) номером k воспринимаемой ячейки

Конфигурацию машины будем записывать так:

здесь r-воспринимаемая ячейка, выделяется в виде дроби.

Если в программе машины для пары (q_i,a_u) пятерка отсутствует, то в таблице на пересечении строки a_u, и столбца q_i ставится прочерк.

Если машина, начав работу с некоторым словом P, записанным на ленте, придет в заключительное состояние, то она называется применимой к этому слову. Результатом ее работы считается слово, записанное на ленте в заключительном состоянии. В противном случае, машина называется не применимой к слову Р.

Пример. Построим машину Тьюринга, складывающую натуральные числа, записанные в унарной системе счисления (т.е. записанные при помощи одного символа |. Например 5=|||||.).

Решение. Рассмотрим алфавит А = <|, +, Λ>.

Машина определяется следующей программой:

Выпишем последовательно возникающие при работе этой машины конфигурации на исходном слове ||+|||, т.е. 2+3. Здесь при записи конфигурации будем использовать следующее соглашение: состояние, в котором находится машина, записывается в круглых скобках справа за обозреваемой буквой.

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

Решение. Искомую машину построим в алфавите A=<|, α, Λ>.

Программа такой машины может выглядеть так:

Применим полученную машину к слову ||.

Введение новой буквы α и замена исходных | на α позволяет различить исходные | и новые (приписанные) |. Состояние q₁ обеспечивает замену | на α, состояние q₂ обеспечивает поиск α, предназначенных для замены на |, и останов машины в случае, когда α не обнаружено, q₃ обеспечивает дописывание | в случае, когда произошла замена α на |.

Источник

Навигация

Календарь

Машина Тьюринга. Задачи и решения

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

Что такое формальный исполнитель? Что значит — один формальный исполнитель имитирует работу другого формального исполнителя? Если Вы играли в компьютерные игры — на экране объекты беспрекословно подчиняются командам играющего. Каждый объект обладает набором допустимых команд. В то же время компьютер сам является исполнителем, причем не виртуальным, а реальным. Вот и получается, что один формальный исполнитель имитирует работу другого формального исполнителя.

Рассмотрим работу Машины Тьюринга.

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

Таким образом Машина Тьюринга формально описывается набором двух алфавитов:

A= — внешний алфавит, служит для записи исходных данных

Q= — внутренний алфавит, описывает набор состояний считывающе-печатного устройства.

Каждая ячейка ленты может содержать символ из внешнего алфавита A = (В нашем случае A=<0, 1>)

Допустимые действия Машины Тьюринга таковы:

1) записать какой-либо символ внешнего алфавита в ячейку ленты (символ, бывший там до того, затирается)

2) сместиться в соседнюю ячейку

3) сменить состояние на одно из обозначенных символом внутреннего алфавита Q

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

Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q = . В начале работы машина Тьюринга находится в состоянии q1. Состояние q0 — это конечное состояние, попав в него, автомат заканчивает работу.

В каждой клетке таблицы, соответствующей некоторому символу 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]\triangleleft[/math]

Многоленточная машина Тьюринга [ править ]

Многоленточная машина с [math]n[/math] дорожками эмулируется многодорожечной машиной с [math]2n[/math] дорожками следующим образом: каждая нечётная дорожка соответствует ленте исходной машины, а на каждой чётной дорожке отмечены специальным символом [math]*[/math] позиция головки на ленте выше (считаем, что ленты нумеруются сверху вниз).

Каждый шаг исходной машины эмулируется конечной последовательностью шагов построенной машины следующим образом: исходно головка находится в позиции самой левой отметки и идёт вправо до самой правой отметки, запоминая прочитанные около символов [math]*[/math] символы в состоянии. Пройдя до самой правой отметки, головка возвращается влево, совершая необходимые действия (переписывая символы около отметок и передвигая сами отметки). После такого прохода головка переходит в следующее состояние, завершая эмуляцию шага.

Аланом Тьюрингом было сформулировано следующее утверждение:

Иными словами, тезис говорит о том, что любой алгоритм можно запрограммировать на машине Тьюринга.

Универсальная машина Тьюринга [ править ]

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

Источник

Применение машин Тьюринга к словам (стр. 4 )

Утверждение (Тезис Чёрча-Тьюринга):

Из за большого объема этот материал размещен на нескольких страницах: 1 2 3 4

5) f(x, y)-? В начальной конфигурации обозревается крайняя правая единица ленты

КОНСТРУИРОВАНИЕ МАШИН ТЬЮРИНГА

5.13. Известно, что на ленте записано слово ; n ³ 1. Постройте машину Тьюринга с внешним алфавитом А = <а0, 1>, которая отыскивала бы левую единицу этого слова (т. е. приходила бы в состояние, при котором обозревалась бы ячейка с самой левой единицей данного слова, и в этом положе­нии останавливалась), если в начальный момент головка машины обозревает одну из ячеек с буквой данного слова.

5.14. Сконструируйте машину Тьюринга с внешним ал­фавитом А = <а0, 1>, которая каждое слово в алфавите А1 = <1>перерабатывает в пустое слово, исходя из стандарт­ного начального положения.

Указание. В алфавит внутренних состояний включите четыре буквы Q= .

5.15. Сконструируйте машину Тьюринга с внешним алфавитом А = <а0, 1>, которая каждое слово длиной п в алфавите A1 = <1>перерабатывает в слово длиной п + 1 в том же алфавите А1.

Указание. Используйте алфавит внутренних состояний из двух букв. См. задачу 5.1.

5.16. На ленте машины Тьюринга записаны два набора единиц 1. Они разделены звездочкой *. Составьте функцио­нальную схему машины так, чтобы она выбрала больший из этих наборов, а меньший стерла, исходя из стандартного на­чального положения (см. задачу 5.2). Звездочка должна быть сохранена, чтобы было видно, какой из массивов выбран.

Указание. Машина может работать, например, следующим обра­зом. Заменить крайнюю правую единицу на a и из состояния q1 перейти в состояние q2, в котором она должна, ничего не меняя, прошагать к край­ней левой единице. Здесь, перейдя в состояние q3, заменить крайнюю левую единицу на букву a. Далее, перейдя в состояние q4, прошагать к крайней правой единице, ничего не меняя. Здесь снова заменить единицу на бук­ву a и вернуться к крайней левой единице и т. д. Дальше программа имеет разветвление. Если, начиная двигаться с правого конца, машина в состоя­нии q1, сделав шаг влево, обозревает ячейку с буквой *, то это означает, что единицы правого массива иссякли. Следовательно, левый массив боль­ше. Тогда машина, перейдя в состояние q5. проходит ячейку с буквой * и во всех последующих ячейках слева проставляет единицы. Затем в со­стоянии q6 она возвращается к ячейке со *, минует ее и следует дальше вправо, стирая содержимое ячеек (там записаны буквы a). Дойдя до пер­вой пустой ячейки, машина останавливается. Если же, начиная двигаться с левого конца, машина в состоящий q3 сделав шаг вправо, обозревает ячей­ку с буквой *, то это означает, что иссякли единицы левого массива. Следовательно, большим оказывается правый массив. Привлекая новые состоя­ния q7 и q8, строим программу аналогично предыдущему ответвлению.

5.17. Постройте машину Тьюринга, которая бы к нату­ральному числу в десятичной системе счисления прибавляла единицу.

Р е ш е н и е. В качестве внешнего алфавита естественно выбрать алфавит, содержащий наименования всех цифр десятичной системы счисления. Конечно же, необходим и пу­стой символ а0. Итак, А =< а0, 1 2, 3, 4, 5, 6, 7, 8, 9, 0>. Состоя­ний у машины будет два: q0 (это, как обычно, остановка) и q1 (рабочее состояние). Итак, Q = . Функциональная схема <программа) машины:

Источник

Решение задач. Машина Тьюринга

Написать программу на машине Тьюринга, прибавляющую число 2 к введенному числу.

Написать на машине Тьюринга программу, прибавляющую 3 к введенному числу.

Перенести первый символ непустого слова P в его конец. Алфавит : A=.

Если первый символ – это a, то надо перейти в состояние q2, в котором автомат бежит вправо и записывает в конце a. Если же первым был символ b, тогда надо перейти в состояние q3, где делается всё то же самое, только в конце записывается символ b. Если же первым был символ c, тогда переходим в состояние q4, в котором автомат дописывает за входным словом символ c.

Для решения этой задачи предлагается выполнить следующие действия:

В противном случае уничтожить всё входное слово ( q ₇ ).

Запомнить первый символ, стереть второй символ и установить на его месте первый.

Сдвиг символов осуществляется так: в очередной клетке записываем b (если в q ₁ ) или c (если в q ₂ ), переходим вправо и меняем состояние на q ₁ (если в текущей клетке было записано b ) или на q ₂ (если было записано c ), где осуществляется дальнейшая запись. Если в очередной клетке записано a или пробел, то записываем в нее запомненный символ и останавливаем программу.

После этого возвращаемся к началу входного слова.

Вначале записываем знак = за входным словом. Затем возвращаемся под первый символ входного слова.

Источник