Постройте машину тьюринга которая бы в слове cabdabda выполнила

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

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

hello html m5bcd6ff6

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

hello html m2e8b9e87

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

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

hello html 7ac47514

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

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

hello html 38de6f62

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

hello html 2e4fa07d

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

hello html m7ae7ccfd

hello html 2379514a

hello html 7f3145bf

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

hello html m47c2d2c5

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

Источник

Календарь

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

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

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

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

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

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

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

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

turing 1

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

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

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

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

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

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

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

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

Источник

Постройте машину тьюринга которая бы в слове cabdabda выполнила

Абстрактные вычислительные машины

Материал взят с ресурса Планета информатики

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

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

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

Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:

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

turing

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

turing2

Здесь происходит сдвиг головки влево до тех пор, пока она не окажется над пустым символом. После этого машина переходит в состояние Q2 (команды которого совпадают с командами Q1 предыдущей программы).

Материал взят с ресурса Планета информатики

t 01

t 02

Решение этой задачи аналогично рассмотренному выше примеру.

t 03

Задача 4 (усложнение задачи 3)

t 04

Те клетки, в которые машина Тьюринга никогда не попадает, оставляем пустыми.

t 05

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

Рассмотрите со школьниками следующие варианты входных слов и попросите их сформулировать, что должна делать машина Тьюринга, каков внешний вид выходного слова, чем с точки зрения машины Тьюринга эти варианты различаются:

Рассмотрим следующие варианты входных слов:

t 06

t 07

t 08 1

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

t 08 2

В этом случае их программа выглядит следующим образом:

t 08 3

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

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

Идея решения (условие останова). На ленте есть два исходных массива штрихов.

t 09 1

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

t 09 2

При решении этой задачи следует обратить внимание на правильное выписывание алфавита:

t 10

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

После программы запуска возможны варианты:

Источник

Постройте машину тьюринга которая бы в слове cabdabda выполнила

Alan Turing

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

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

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

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

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

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

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

turing 1

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

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

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

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

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

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

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

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

Источник

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

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

1504337777ljnaw

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

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

5.13. Известно, что на ленте записано слово image018 15; 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 = . Функциональная схема <программа) машины:

Источник

Оцените статью
AvtoRazbor.top - все самое важное о вашем авто