Задачи на машину тьюринга с решениями

Задачи на машину тьюринга с решениями

Alan Turing

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

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

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

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

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

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

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

turing 1

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

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

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

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

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

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

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

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

Источник

Задачи на машину тьюринга с решениями

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

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

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

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

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

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

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

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

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

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

Источник

Календарь

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

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

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

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

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

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

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

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

turing 1

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

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

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

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

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

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

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

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

Источник

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

Онлайн-конференция

«Современная профориентация педагогов
и родителей, перспективы рынка труда
и особенности личности подростка»

Свидетельство и скидка на обучение каждому участнику

Написать программу на машине Тьюринга, прибавляющую число 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

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

Источник

Примеры выполнения заданий. Практическое занятие №17

Практическое занятие №17. Машина Тьюринга.

В каждый момент времени рабочая головка обозревает одну ячейку ленты и выполняет следующие действия:

1) заменяет символ в обозреваемой ячейке новым (возможно, прежним);

2) переходит в новое состояние (возможно, в прежнее);

3) сдвигается на одну ячейку (вправо R или влевоL) либо остается на месте H.

Совокупность команд будем называть программой машины Тьюринга.

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

Под конфигурацией машины Тьюринга мы понимаем распределение букв алфавита А по ячейкам ленты, состояние головки и обозреваемую ячейку. Работа машины Тьюринга по программе состоит в смене конфигураций. Конфигурацию в момент времени ti будем обозначать Kti. Если эта конфигурация не является заключительной, то машина в соответствии со следующей командой переходит в конфигурацию Kti+1.

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

1. Пусть требуется добавить 1 к натуральному числу n, представленному на ленте машины Тьюринга в двоичной системе счисления, то есть в алфавите <0,1>.

Решение: внешний алфавит машины будет следующим: <L, 0, 1>.

Будем считать начальной следующую конфигурацию: Lq1s1…spL. Для того, чтобы прибавить 1 к двоичному числу n сначала необходимо «отогнать» головку машины вправо и установить ее под последней (самой младшей) цифрой двоичного числа. Если последняя цифра числа есть 0, то достаточно заменить 0 на 1 и завершить процесс, то есть перевести головку (машину) в заключительное состояние q0.

Если же последняя цифра числа есть 1, то необходимо заменить ее на 0, а головку сдвинуть влево, чтобы «увидеть» следующий разряд двоичного числа. Если окажется, что этот разряд содержит 0, то заменить 0 на 1 и опять-таки перевести головку (машину) в заключительное состояние q0. Если же этот разряд содержит 1, необходимо заменить ее на 0 и опять сдвинуть головку влево. И так далее, до тех пор, пока либо не встретится разряд, содержащий 0, либо головка дойдет до первого слева пустого символа L. В любом из этих случаев 0 или L следует заменить на 1 и перевести головку (машину) в заключительное состояние q0.

Программа машины, прибавляющей 1 к двоичному числу, имеет вид:

q11 ®q11R q10 ®q10R q1L ®q2LL q20 ®q31H q21 ®q20L q2L ®q01H q31 ®q31L q30 ®q30L q3L ®q0LR.

Решение: в качестве внешнего алфавита машины берем алфавит:<L, |, 0,1>.

Опишем алгоритм решения задачи в словесной форме:

1. «Отогнать» головку машины влево до первого пустого символа, заменить этот символ нулем (0).

2. «Отогнать» головку машины вправо до последней черточки, заменить ее пустым символом. Запомнить, что 1 из унарного представления числа n вычтена.

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

4. Пункты 2 и 3 повторять до тех пор, пока не исчерпается исходное число, то есть на ленте не останется «палочек».

5. Головку отогнать в крайнюю левую позицию полученного двоичного числа и остановить машину.

Программа работы машины имеет вид:

q1| ®q1|L q1L®q20R q2| ®q2|R q2L ®q3LL q3| ®q4 LL q4 | ®q4|L q40 ®q51R q41®q40L q4 L®q51R q51 ®q51R q50 ®q50R q5| ®q2|H q5 L ®q6 LL q61 ®q61L q60 ®q60L q6 L ®q0LR

3. Составьте программу машины Тьюринга, подсчитывающую число вхождений символа a в слово Р в алфавите .

Решение: пусть начальная конфигурация машины имеет вид q1P.

Надо перевести ее в конфигурацию q0n*P, где n – двоичное число, выражающее число вхождений символа a в слово Р в алфавите <a, b, c>.

Опишем алгоритм решения задачи в словесной форме:

1. Слева от слова Р приписываем символы 0 и *.

3. Повторяем п. 2 до тех пор, пока не пройдем все слово P.

4. Убираем все штрихи в слове Р.

5. Устанавливаем головку машины под крайней левой цифрой двоичного числа n и останавливаем машину.

Программа работы машины имеет вид:

q1a ® q2aL q1b ® q2bL q1c ® q2cL q2L ® q3*L q3L ® q40R q40 ® q40R q41 ® q41R q4*® q5*R q55bR q5c® q5cR q5a ’ ®q5a ’ R q56a ’ H q6b® q6bL q6c ® q6cL q6a ’ ® q6a ’ L q6* ® q6*L q60 ® q41R q61 ® q60L q6L ® q41L q5L® q7LL q7a ® q7aL q7b ® q7bL q7c ® q7cL q7a ’ ® q7aL q7* ® q7*L q70 ® q70L q71 ® q71L q7L ® q0LR

Задания для самостоятельного выполнения

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Источник

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