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

Машина Тьюринга.

Минимизация ДНФ. | Табличный способ задания. | Графический способ задания. | Логика предикатов. Кванторы. | Пример тождественно истинного предиката: . | Элементы теории графов. | Матрицы графов. | Некоторые общие понятия теории графов. | Взвешенные графы и алгоритмы поиска кратчайшего пути. | Задача о кратчайших путях. |


Читайте также:
  1. А когда ты там в последний раз был? — С невинным видом поинтересовался Мелифаро. Я машинально наморщил лоб, пытаясь припомнить.
  2. Бердяев Н. Человек и машина.
  3. Богдан машинально, не будучи в состоянии отвести взор от ловцов сельди, кивнул.
  4. Богдан остановился, вдруг сбившись с дыхания. Машинально поправил очки.
  5. Вылетаю на мороз, поскальзываюсь и падаю на пятую точку, ударяясь копчиком. Слезы капают на куртку, я поднимаюсь, передо мной тормозит машина, и передняя дверь сразу открывается.
  6. Группа 133 Уплотнение грунта грунтоуплотняющими машинами со свободно падающими плитами
  7. ДА-НЕТНАЯ МАШИНА

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

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

Бесконечную в обе стороны ленту, разделенную на ячейки В каждой ячейке может быть записан один из символов рабочего алфавит а машины .Любой алфавит должен содержать пустой символa0 = Λ< запись которого означает отсутствие информации в данной ячейке. Совокупность символов алфавита, записанных на ленте, называется словом.

Считающее - записывающее устройство (СЗУ).

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

Управляющее устройство (УУ).

УУ руководит действиями СЗУ в соответствии с программой Р. При этомУУ может находиться в одном из состояний Q = {q1, q2,... qn, q0 }, среди которых должно быть обязательно выделено начальное состояние q1 и заключительное состояние q0. Действия УУ зависит от входящих в программу команд, от текущего состояния УУ и от символа, записанного в обозреваемой в данный момент ячейке. Будем считать, что это крайняя левая непустая ячейка.

Программа Р.

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

где q, r Q, a, b A.

Программа через УУ сообщает, что должна делать СЗУ в случае, если состояние УУ равно q Q (q ≠ q0), и в обозреваемой ячейке записан символ а А. УУ находит команду с левой частью qa и действует следующим образом,

а) если правая часть этой команды равна br, то М записывает в обозреваемую ячейку b, и УУ переходит в состояние r;

b) если правая часть этой команды равна bRr или bLr, то М записывает в обозреваемую ячейку b, головка сдвигается на одну ячейку вправо или влево соответственно, и УУ переходит в состояние r.

Формально, машина Тьюринга – это тройка М = (А, Q, P), где:

А – алфавит машины (т.е. символы, которые записываются в ячейки, включая пустой символ а0 = Λ);

Q – конечное множество состояний УУ, содержащее два выделенных элемента q1 и q0;

Р – множество команд УУ, которое называется программой машины.

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

П р и м е р 1.

Применима ли машина Тьюринга М, заданная программой Р, к слову S? Если применима, то найти результат применения машины Тьюринга к данному слову.

 

 

где верхняя строка – это записанное на ленте слово, нижняя строка показывает, какая в данный момент ячейка обозревается, и в каком состоянии находится УУ.

Найдем результат применения машины к слову S.

В начальный момент, как видно из таблицы, СЗУ обозревает символ 1 и УУ находится в состоянии q1. Находим в программе команду с левой частью q11. Это команда Она означает, что в рассматриваемую ячейку записывается 0, головка сдвигается на одну ячейку вправо, и УУ устанавливается в состояние q1. В результате применения этой команды имеем:

Снова обозревается символ 1 и УУ находится в состоянии q1. В обозреваемую ячейку записывается 0, головка сдвигается на одну ячейку вправо и остается в состоянии q1. Получим

В этот раз обозревается символ 0 и УУ находится в состоянии q1. Соответствующая команда в программе имеет вид q10 → 1Rq1, поэтому в обозреваемую ячейку записывается 1, головка сдвигается на одну ячейку вправо, и УУ остается в состоянии q1.

На следующем шаге обозревается символ 1 и УУ находится в состоянии q1. выполняется команда

q11 → 0Rq1:

Далее обозревается пустая ячейка Λ, и УУ находится в состоянии q1. Соответствующая команда имеет вид q1Λ → ΛLq2:

Далее, согласно программе, головка движется влево вдоль всего слова, не изменяя записанные в ячейках символы до тех пор, пока не примет следующее положение

 

 

В этом случае соответствующая команда имеет вид q2Λ → ΛRq0. Это означает, что обозреваемая ячейка остается пустой, головка сдвигается вправо и переходит в состояние q0.

Состояние q0 – заключительное, поэтому машина заканчивает работу, т.е. машина применима к слову S. Чтобы узнать результат применения, рассмотрим непустые символы на ленте, которые мы получили. Увидим, что слово S преобразовано в слово S′ = 0010.

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

Программу машины можно задать таблично.

 

 

 

П р и м е р 2.

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

Расширим исходный алфавит А ={ | } до А′ ={ |, α }. искомую машину построим в алфавите А′ {Λ}. Программа машины будет выглядеть так

 

 

При работе машина считывает букву в обозреваемой ячейке и находит клетку в таблице, соответствующую считанной букве (|, α, Λ) и состоянию машины (qi). ± сдвиг головки соответственно вправо или влево.

Применим машину к слову | |.

 

1)

 

2)

 

3)

 

4)

 

5)

 

 

6)

 

 

7)

 

 

8)

 

9)

 

10)

 

 

11)

 

 

12)

 

13)

 

14)

 

 

15)

Состояние q0 – заключительное, поэтому машина заканчивает работу.

Введение новой буквы α и замена исходных | на α позволяет различать исходные | и новые (приписанные). Состояние q1 обеспечивает замену | на α, состояние q2 обеспечивает поиск α, предназначенных для замены на |, и останов машины, если α не обнаружено, q3 обеспечивает дописывание | в случае, когда произошла замена α на |.

Существуют следующие стандартные машины Тьюринга.

1. Тождественная машина Е – применима к любому слову u над алфавитом А и E(u) = u.

2. Пусть А - алфавит и ▲А (▲ – неподвижный ограничитель), n N. Копирующей машиной Кn называется машина, применимая к любому слову u A, причем

Kn (u) = u▲, u▲,.... u▲.

n – раз

3. Пусть А – алфавит и (α. β) А (α ≠ β). Машиной, заменяющейα на β, называется машина Зα←β, применимая к любому слову u, так что

Зα←β(u) =

Теорема. Тождественная. копирующая и заменяющая машины существуют.


Дата добавления: 2015-07-20; просмотров: 70 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Понятие автомата.| Автомат Мили.

mybiblioteka.su - 2015-2024 год. (0.015 сек.)