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

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

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

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

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

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

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

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

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

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

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

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

Источник

Машина Тьюринга. Удвоить слово P (например: abb → abbabb)

Машина Тьюринга: удвоить каждую букву в каждом слове
Написать программу для машины Тьюринга, которая каждое слово _<1>_<2>. _ в алфавите.

Машина Тьюринга. Если слово P содержит одновременно символы a и b, то заменить P на пустое слово
Если слово P содержит одновременно символы a и b, то заменить P на пустое слово.

Машина Тьюринга. В итоговом ответе записать что получившиеся слово = a0 a0 a0 a0 a0 или слово = 0
Я решил задачу: После применения машины Тьюринга к слову a=11*11, у меня вышло после применения.

Машина Тьюринга. Выдать в качестве ответа слово 1, если число Q больше числа R, и слово 0 иначе
Пусть P имеет вид Q>R, где Q и R – непустые слова из символов 0 и 1. Трактуя Q и R как записи.

Решение

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

2. Можно реализовать вариант с большими буквами. Сначала заменить ВСЕ символы исходной строки на большие, а потом каждый большой заменять на маленький, приписывая к строке его копию. Когда большие символы закончатся, задача решена.

Машина Тьюринга: развернуть слово
Нужна таблица (программа) переворачивающая слово машина Тьюринга пример из (abb) сделать (bba)

Машина Тьюринга. Перевернуть слово.
Нужно составить машину Тьюринга, которая бы переворачивала любое четырёхбуквенное слово. Алфавит.

Машина Тьюринга. Восстановить закодированное слово
Дан алфавит и номер слова, закодированного в этом алфавите. Восстановить закодированное.

Найти слово на ленте. Машина Тьюринга
Здравствуйте! Нужно написать алгоритм поиска слова на ленте. Другими словами, его расположение на.

Машина Тьюринга. Определить, входит ли в слово P символ a
7. A=. Определить, входит ли в слово P символ a. Ответ: слово из одного символа a (да.

Источник

Навигация

Календарь

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей
· символ из алфавита A
· направление перемещения: «>» (вправо), «

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей
· символ из алфавита A
· направление перемещения: «>» (вправо), «

Источник

Применение машин Тьюринга к словам (стр. 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 = . Функциональная схема <программа) машины:

Источник