Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Примеры

Читайте также:
  1. III. Первоначальное накопление капитала (особенности, примеры)
  2. Билет№69. Прямое доказательство, его специфика. Привести примеры.
  3. Билет№71. Косвенное доказательство (от противного). Привести примеры.
  4. Билет№72. Разделительное доказательство, привести примеры.
  5. Виртуальные методы. Функциональное назначение. Примеры применения.
  6. Влияние диверсификации на риск портфеля ценных бумаг . Привести примеры расчетов.
  7. Глобальные проблемы атмосферы. Приведите примеры
  8. Дайте определение учению чучхе и приведите примеры его реализации в КНДР.
  9. Ещё примеры
  10. Жизненный цикл плоских червей. Чередование хозяев и феномен смены хозяев. Промежуточные и основные хозяева. Понятие о биогельминтах, примеры.

1. Разработать программу для перевода числа, записанного в унарной системе счисления, в двоичную систему счисления. Машина начинает работу над унарным словом, записанным на ленте, в состоянии q1, а записывающая-считывающая головка обозревает крайний левый символ унарного слова. По окончании работы программы машина должна находиться в состоянии q0,,а записывающая-считывающая головка обозревать крайний левый символ двоичного слова, записанного на ленте.

Число К в унарной системе счисления обозначается словом Q=(//…/), где символ «/» повторяется К раз.

В этой задаче Авх={/}, Авых = {0,1}, L - пустой символ. Построим программу П, решающую данную задачу. Рабочий алфавит машины Т - A={/,L,0,1}. Работу программы организуем циклически. Пусть к началу k -го цикла на ленте выписано слово PQ, где Р - двоичная запись уже считанной части числа К, Q - остаток унарного слова, Q =/(n–k), т.е. последовательность (n-k) унарных символов. После выхода из этого цикла на ленте должно быть написано слово P`Q`, где Р` - -двоичная запись числа К+1, Q`- остаток унарного слова, равный /(n–k-1). В течение k -го цикла из Q удаляется один унарный символ /, а к двоичной записи Р прибавляется 1 в двоичной системе счисления. При этом записывающая (считывающая) головка проходит слово PQ (непустое) слева направо, используя команды

q1 1 q1 R, q1 q1 R, q1 /q1 / R, q1 Lq2 L L.

Последняя команда «нащупала» конец слова и вернула головку на последнюю букву в состоянии q2. Далее головка стирает эту букву, если это /, и запоминает необходимость прибавления 1 к двоичному числу Р при помощи команды q2/ q3LL.

Затем головка возвращается влево до начала двоичного слова Р, используя команду q3/q3/L и осуществляет двоичное прибавление 1 к слову Р в соответствии с правилами двоичного сложения. Это работа выполняется подпрограммой

q31q3L; q3q41L; q4 0 q4 0 L; q41q4 1 L; q4Lq1 L R; q3Lq11 S.

После завершения работы по приведенному фрагменту программы сложение окончено, и записывающая-считывающая головка расположена над первой буквой слова Р. Осталось описать выход из цикла, когда все унарные символы стерты. В этом случае работают команды: q21q01 S; q2 q S.

Заметим, что в приведенном списке отсутствуют команды, которые не могут понадобиться в процессе работы. Их вид безразличен и может быть задан произвольно. Полностью программа машины Тьюринга: выполняющая перевод чисел из унарной системы счисления в двоичную систему счисления, представлена в табл. 14.

Таблица 14 Программа машины Тьюринга, выполняющей перевод числа из унарной системы счисления в двоичную систему счисления

Q A q1 q2 q3 q4
/ q1 / R q3 LL q3 / L -
  q1 1 R q 01 S q 30 L q4 1 L
  q1 0 R q0 0 S q4 1 L q4 0 L
L q 2 LL - q1 1 S q 1 LR

 

В качестве примера работы программы рассмотрим работу машины над словом P=(/////), содержащим пять унарных символов:

q 1///// ├ ///// q1 L ├ //// q 2 / ├ /// q 3 / L ├ q 3 L//// ├ q11//// ├ 1 /// q2 / ├

1// q3 / L ├ q3 1 /// ├ ├ q3L0/// ├ q110 /// ├ 10 // q2 / ├ 10 / q3 / L ├ 1q 3 0// ├ q411 // ├ q4L11// ├ L q 111// ├ ├ 11| q2 / ├ 11 q3 / L ├ 1q3 1 / ├ q310 / ├

q3 L 00/ ├ q1100 / ├ 100q2 / ├ 10q30 ├ 1q401 ├ q4 101 ├ q4 L101 ├ L q1101├ 10q21├ 10q0 1.

Результат применения машины Тьюринга, заданной предложенной программой, к записанному на ленте слову, состоящему из пяти унарных символов, равен 1012=510. В формальной записи - Т(/////)= 101.

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

Рассмотрим алфавит Построим машину Тьюринга, удовлетворяющую следующему условию:

Пусть, например, m=5, n=3. Слово, записанное на ленте в начале работы машины, будет иметь вид

Λ/////+///Λ.

Записывающая-считывающая головка установлена над крайним левым символом слова, записанного на ленте, Управляющее устройство находится в начальном состоянии q1. В конце работы машины над словом на ленте должно быть записано восемь унарных символов, управляющее устройство должно находиться в заключительном состоянии q0, записывающая-считывающая головка должна обозревать крайний левый символ слова на ленте.

Программа, реализующая выполнение этих действий, может включать следующие шаги. Машина начинает работу в начальном состоянии q1, подтверждает унарный символ /, содержащийся в обозреваемой ячейке, и, оставаясь в состоянии q1, перемещается на одну ячейку вправо. При этом выполняется команда q1/q1/R. Дойдя до ячейки, в которую записан символ +, машина записывает в эту ячейку унарный символ, выполняя команду q1+q1/R, и затем продолжает движение вправо до тех пор, пока не «нащупает» конец слова, т.е. пустую ячейку (с символом Λ). К этому времени число унарных символов на ленте окажется на единицу больше суммарного числа исходных унарных символов. Поэтому один символ необходимо стереть. Для этого необходимо вернуть головку к ячейке, в которую записан последний унарный символ, выполнив команду q1Λq2ΛL. Новое состояние q2 позволит стереть унарный символ в обозреваемой ячейке, выполнив команду q2/q3ΛL. Теперь на ленте записано нужное число унарных символов. Новое состояние q3 предназначено для перемещения головки влево без изменения содержимого ячеек, команда q3/q3/L.

«Нащупав» конец слова слева, можно перейти в заключительное состояние q0 с помощью команды q3Λq0ΛR. При этом головка окажется над крайней левой ячейкой записанного на ленте слова.

Программа машины Тьюринга может быть представлена табл.15.

Таблица 15 Программа машины Тьюринга, выполняющей сложение унарных чисел

  q1 q2 q3
/ /q1R Λq3L /q3L
+ /q1R * *
Λ Λq2L * Λq0R

Последовательность конфигураций, проходимых машиной в работе над словом запишется следующим образом:

q1/////+/// ├/q1////+/// ├ //q1///+/// ├ ///q1//+/// ├ ////q1/+/// ├

├ /////q1+/// ├ //////q1/// ├ ///////q1// ├ ////////q1/ ├ /////////q1Λ ├

├ ////////q2/ ├ ///////q3 /Λ ├ //////q3// ├ /////q3/// ├ ////q3////

├ ///q3///// ├ //q3////// ├ /q3////// ├ q3//////// ├ q3Λ//////// ├ q0////////.

Результатом работы машины над словом, записанным на ленте, является новое слово, содержащее восемь унарных символов. Записывающая - считывающая головка находится над крайней левой буквой заключительного слова. Управляющее устройство перешло в заключительное состояние q0.




Дата добавления: 2014-11-24; просмотров: 145 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав