Мт

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

Надеюсь все ознакомились c «подгоном Титова» по лр 5 (файл turmar.pdf)

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

Чтобы не возникло путаницы: Машиной Тьюринга также называют любой набор правил, который направлен на решение какой-то задачи с использованием МТ как алгоритмической машины. Поэтому внимательно читайте что от вас требуют. Машиной Тьюринга можно назвать как алгоритм, так и реальную здоровую махину с лентой на перевес.

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

Теперь обо всем по порядку.

Лента МТ— условно бесконечная, разбитая на ячейки полоска.(Условно, т.к. физически она конечна) На всех рисуночках выглядит так:

%d0%bb%d0%b5%d0%bd%d1%82%d0%b0

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

Алфавит МТ— все символы, которые могут встречаться на ленте. Допустим на примере сверху алфавит выглядит так: A={ λ , a , b }. Где λ-пробел.

Команды МТ-набор правил. Собственно это и есть то, что требует от нас препод: написать набор правил для МТ, который реализует поставленную задачу.

Распространены 2 типа команд:

  1. В четверках
  2. В пятерках

Сейчас все поймете. Каждая отдельная команда в общем случае выглядит так:

(4) q0, a, s|d, q’

(5) q0, a, s, d, q’

q0-состояние в котором СГ сейчас находится

a-символ, который видит СГ

s-символ, который СГ запишет сейчас на место a

d-действие, которое сделает СГ после записи

q’-состояние, в которое оно перейдет после действия

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

Отличие 4-к от 5-к:

  • В 4-х МТ либо записывает символ, либо делает действие за один такт.
  • В 5-х МТ и записывает символ в ячейку и делает действие за один такт.

(Такт или Цикл — одна выполненная команда)

Возможные действия МТ:
r (>) — движение головки вправо;
l (<) — движение головки влево;
= — отсутствие движения на данном такте;
! (#) — полная остановка машины.

В разных интерпретаторах МТ действия могут различаться по обозначению, но суть не меняется, всего 4 доступных действия.

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

В примере используется эмулятор МТ в четверках. (оффлайн  версия тут)

Задача: заменить 0 на 1, и наоборот во всем слове.

Решение:

  1. Если СГ увидит 0, она должна заменить ее на 1
  2. Если СГ увидит 1, она должна заменить ее на 0

Итак, команды (подходят для эмулятора сверху)

00 , , < , rep

(выходим из нулевого состояния 00, затем, если СГ видит λ (пробел), то она просто передвигается налево и передает управление на состояние rep. rep-просто название, тут может быть и цифра и буква в данном эмуляторе)

rep,0,1,mov

(если ГС перешла в состояние rep, то МТ начинает искать команду, у которой входное состояние rep, а символ, который она видит соответствует тому, что определен в rep. Внимание, команд rep должно быть столько же, сколько и символов в вашем алфавите. Чтобы при виде любого символа СГ могла найти нужную последовательность действий для данного состояния)

(Так, СГ нашла 0 в состоянии rep, значит определив команду выше, мы скажем ей, что при виде 0 в состоянии реп, запиши в ячейку 1 и перейди в состояние mov)

mov,1,<,rep

(В состоянии mov, при виде 1, СГ должна будет просто перейти на ячейку слева и передать управление снова состоянию rep)

Делаем те же самые команды для МТ в случае, если СГ встретит 1:

rep,1,0,mov

mov,0,<,rep

Такими темпами, МТ заменит все 0 на 1 (и наоборот) и приедет в конец слова.

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

rep, ,>,fin

(если rep нашел пробел, значит слово закончилось, дальше слева ничего нет, значит время возвращаться заканчивать с этой дичью)

(Завершить работу МТ можно где вам угодно. Именно в этой задаче было решено завершить выполнение рабочего цикла МТ на входной ячейке)

fin,0,>,fin
fin,1,>,fin
fin, ,#,fin

Итак, вся прога выглядит так:

00, ,<,rep

rep,0,1,mov
rep,1,0,mov
rep, ,>,fin

mov,0,<,rep
mov,1,<,rep

fin,0,>,fin
fin,1,>,fin
fin, ,#,fin

Давайте посмотрим что сделает со строкой 00000001 наша машина:

1234

Аналогичный результат в другом эмуляторе:

5

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

Почему я разбирал именно в 4-х? Потому что из 4-к команды легко переписать в 5-ки, совершенно ничего не добавляя, кроме команды «остаться на этой ячейке» на место d.

Ну вот, например:

(4) rep,0,1,mov ~  rep,0,1,=,mov (5)

А вот обратно не получится. Однозначно можно только транспонировать 4->5.

Как и обещал, эмуляторы:

~1~ или оффлайн версия (JavaScript)

~2~

~3~ (windows)

 ~4~ (windows)

Интерпретаторам и консольному выводу результата работы МТ на дедовских пк я отведу отдельную статейку.

 

 

 

maxspt

Оставить отклик

Ваш адрес эл.почты не будет опубликован.