русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

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


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


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

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

Бесконечную в обе стороны ленту, разделенную на ячейки В каждой ячейке может быть записан один из символов рабочего алфавита машины .Любой алфавит должен содержать пустой символ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) =

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



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


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.01 сек.