Постройте машину тьюринга которая бы в слове cabdabda выполнила
Решение задач. Машина Тьюринга
Написать программу на машине Тьюринга, прибавляющую число 2 к введенному числу.
Написать на машине Тьюринга программу, прибавляющую 3 к введенному числу.
Перенести первый символ непустого слова P в его конец. Алфавит : A=
Если первый символ – это a, то надо перейти в состояние q2, в котором автомат бежит вправо и записывает в конце a. Если же первым был символ b, тогда надо перейти в состояние q3, где делается всё то же самое, только в конце записывается символ b. Если же первым был символ c, тогда переходим в состояние q4, в котором автомат дописывает за входным словом символ c.
Для решения этой задачи предлагается выполнить следующие действия:
В противном случае уничтожить всё входное слово ( q 7 ).
Запомнить первый символ, стереть второй символ и установить на его месте первый.
Сдвиг символов осуществляется так: в очередной клетке записываем b (если в q 1 ) или c (если в q 2 ), переходим вправо и меняем состояние на q 1 (если в текущей клетке было записано b ) или на q 2 (если было записано c ), где осуществляется дальнейшая запись. Если в очередной клетке записано a или пробел, то записываем в нее запомненный символ и останавливаем программу.
После этого возвращаемся к началу входного слова.
Вначале записываем знак = за входным словом. Затем возвращаемся под первый символ входного слова.
Навигация
Календарь
Машина Тьюринга. Задачи и решения
Один из важнейших вопросов современной информатики — существует ли формальный исполнитель, с помощью которого можно имитировать любого формального исполнителя. ответ на этот вопрос был получен почти одновременно двумя выдающимися учеными — А. Тьюрингом и Э. Постом. Предложенные ими исполнители отличались друг от друга, но оказалось, что они могут имитировать друг друга, а главное — имитировать работу любого формального исполнителя.
Что такое формальный исполнитель? Что значит — один формальный исполнитель имитирует работу другого формального исполнителя? Если Вы играли в компьютерные игры — на экране объекты беспрекословно подчиняются командам играющего. Каждый объект обладает набором допустимых команд. В то же время компьютер сам является исполнителем, причем не виртуальным, а реальным. Вот и получается, что один формальный исполнитель имитирует работу другого формального исполнителя.
Рассмотрим работу Машины Тьюринга.
Машина Тьюринга представляет собой бесконечную ленту, поделенную на ячейки, и каретку (считывающе-печатающее устройство), которая движется вдоль ленты.
Таким образом Машина Тьюринга формально описывается набором двух алфавитов:
A=
Q=
Каждая ячейка ленты может содержать символ из внешнего алфавита A =
Допустимые действия Машины Тьюринга таковы:
1) записать какой-либо символ внешнего алфавита в ячейку ленты (символ, бывший там до того, затирается)
2) сместиться в соседнюю ячейку
3) сменить состояние на одно из обозначенных символом внутреннего алфавита Q
Машина Тьюринга — это автомат, который управляется таблицей.
Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q =
В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей
· символ из алфавита A
· направление перемещения: «>» (вправо), «
Постройте машину тьюринга которая бы в слове cabdabda выполнила
Абстрактные вычислительные машины
Материал взят с ресурса Планета информатики
То есть, всякий интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга.
Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой. Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:
Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния).
Можно усложнить программу. Допустим, головка располагается не обязательно над первым, а над любым символом слова. Тогда программа для данной машины Тьюринга может быть такой (а могла бы быть и другой):
Здесь происходит сдвиг головки влево до тех пор, пока она не окажется над пустым символом. После этого машина переходит в состояние Q2 (команды которого совпадают с командами Q1 предыдущей программы).
Материал взят с ресурса Планета информатики
Решение этой задачи аналогично рассмотренному выше примеру.
Задача 4 (усложнение задачи 3)
Те клетки, в которые машина Тьюринга никогда не попадает, оставляем пустыми.
Решение этой задачи обычно вызывает у школьников затруднение. При разборе решения этой задачи можно пойти, например, следующим путем.
Рассмотрите со школьниками следующие варианты входных слов и попросите их сформулировать, что должна делать машина Тьюринга, каков внешний вид выходного слова, чем с точки зрения машины Тьюринга эти варианты различаются:
Рассмотрим следующие варианты входных слов:
Однако, как ни странно, решение этой задачи вызывает большие трудности. Очень часто ученики строят машину Тьюринга, которая выполняет циклические действия: последовательно пододвигают правые n штрихов к левым.
В этом случае их программа выглядит следующим образом:
На примере этой задачи четко видно, как часто дети пытаются решить задачу уже знакомыми способами. Мне кажется, что, предлагая ученикам задачи на составление машин Тьюринга, мы развиваем способность к нахождению необычных решений, развиваем способность творчески думать!
Эта задача кажется школьникам достаточно легкой, но трудности возникают с остановом машины Тьюринга. Ниже приведен один из возможных вариантов машины Тьюринга для этой задачи.
Идея решения (условие останова). На ленте есть два исходных массива штрихов.
Опишем сначала состояния машины Тьюринга, которые необходимы для решения нашей задачи, а затем составим программу-таблицу.
При решении этой задачи следует обратить внимание на правильное выписывание алфавита:
Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и её начальное состояние (то есть состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из пронумерованных не обязательно упорядоченных строк команд, если в каждой команде указана строка, на которую нужно перейти. Обычно принимается, что если в команде переход не указан, то переход происходит на следующую строку. Каждая команда имеет следующий синтаксис:
После программы запуска возможны варианты:
Постройте машину тьюринга которая бы в слове cabdabda выполнила
Один из важнейших вопросов современной информатики — существует ли формальный исполнитель, с помощью которого можно имитировать любого формального исполнителя. ответ на этот вопрос был получен почти одновременно двумя выдающимися учеными — А. Тьюрингом и Э. Постом. Предложенные ими исполнители отличались друг от друга, но оказалось, что они могут имитировать друг друга, а главное — имитировать работу любого формального исполнителя.
Что такое формальный исполнитель? Что значит — один формальный исполнитель имитирует работу другого формального исполнителя? Если Вы играли в компьютерные игры — на экране объекты беспрекословно подчиняются командам играющего. Каждый объект обладает набором допустимых команд. В то же время компьютер сам является исполнителем, причем не виртуальным, а реальным. Вот и получается, что один формальный исполнитель имитирует работу другого формального исполнителя.
Рассмотрим работу Машины Тьюринга.
Машина Тьюринга представляет собой бесконечную ленту, поделенную на ячейки, и каретку (считывающе-печатающее устройство), которая движется вдоль ленты.
Таким образом Машина Тьюринга формально описывается набором двух алфавитов:
A=
Q=
Каждая ячейка ленты может содержать символ из внешнего алфавита A =
Допустимые действия Машины Тьюринга таковы:
1) записать какой-либо символ внешнего алфавита в ячейку ленты (символ, бывший там до того, затирается)
2) сместиться в соседнюю ячейку
3) сменить состояние на одно из обозначенных символом внутреннего алфавита Q
Машина Тьюринга — это автомат, который управляется таблицей.
Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q =
В каждой клетке таблицы, соответствующей некоторому символу 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 =