Главная   Онлайн инструменты по математической логике   Мат. логика теория   Как считает компьютер?   Схемы для ЭВМ    

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

Определение булевой функции
Элементарные булевы функции
Задание булевых функций посредством элементарных
Существенные и несущественные переменные
Эквивалентные функции
Основные эквивалентности
Функциональная полнота
Нормальные формы
Совершенные нормальные формы
Минимизация ДНФ методом Квайна
Карты Карно
Полином Жегалкина
Высказывания
Предикаты
Кванторы
Определение формальной теории
Исчисление высказываний
Теорема о дедукции. Полнота ИВ
Автоматическое доказательство теорем
Метод резолюций в ИВ
Определение алгоритма
Машина Тьюринга
Рекурсивные функции
Алгоритмически неразрешимые задачи
Алгоритмы и их сложности



     Машина Тьюринга представляет собой (абстрактное) устройство, состоящее из ленты, управляющего устройства и считывающей головки.
     Лента разбита на ячейки. Во всякой ячейке в точности один символ из внешнего алфавита A={a0,a1...an}. Некоторый символ (будем обозначать его Λ) алфавита A называется пустым, а любая ячейка, содержащая в данный момент пустой символ, называется пустой ячейкой (в этот момент). Лента предполагается потенциально неограниченной в обе стороны.
     Управляющее устройство в каждый момент времени находится в некотором состоянии qj, принадлежащем множеству Q={q0,q1...qm} (m=l). Множество Q называется внутренним алфавитом. Одно из таких состояний (обычно q0) называется заключительным, а некоторое другое (обычно q1) -начальным.
     Считывающая головка перемещается вдоль ленты так, что в каждый момент времени она обозревает ровно одну ячейку ленты. Головка может считывать содержимое обозреваемой ячейки и записывать в нее вместо обозреваемого символа некоторый новый символ из внешнего алфавита A (возможно тот же самый).
     В процессе работы управляющее устройство в зависимости от состояния, в котором оно находится и символа, обозреваемого головкой, изменяет свое внутреннее состояние q. Затем выдает головке приказ напечатать в обозреваемой ячейке определенный символ из внешнего алфавита A, а потом приказывает головке либо остаться на месте, либо сдвинуться на одну ячейку вправо, либо сдвинуться на одну ячейку влево. Попав в заключительное состояние, машина прекращает работу.
     Конфигурацией на ленте (или машинным словом) называется совокупность, образованная:
         1) последовательностью ai(1),ai(2)...ai(s) символов из внешнего алфавита А, записанных в ячейках ленты, где ai(1) - символ записанный в первой ячейке слева и т.д. (любая такая последовательность называется словом)
         2) состоянием внутренней памяти qr
         3) номером k воспринимаемой ячейки
     Конфигурацию машины будем записывать так:
         ai(1),ai(2)...ai(r-1)(ai(r)/qr)ai(r+1),ai(r+2)...ai(s)
здесь r-воспринимаемая ячейка, выделяется в виде дроби.
     Если машина, находясь во внутреннем состоянии qi, воспринимает ячейку с символом au, записывает к следующему моменту времени в эту ячейку символ ar, переходит во внутреннее состояние qs и сдвигается по ленте, то говорят, что машина выполняет команду qiau→qsarS, где символ S может принять одно из значений: -1 - сдвиг головки влево; +1 - сдвиг головки вправо; 0 - головка остается на месте. Список всех команд (пятерок), определяющих работу машины Тьюринга, называется программой этой машины. Программу машины часто задают в виде таблицы. Так для описанной выше ситуации в таблице на пересечении строки ai и столбца qi будет стоять qsarS.

 q0...qi...qm
...     
au  qsarS  
...     

     Если в программе машины для пары (qi,au) пятерка отсутствует, то в таблице на пересечении строки au, и столбца qi ставится прочерк.
     Итак, машина Тьюринга есть, по определению, набор М=(А,Q,П), где А - внешний алфавит, Q - алфавит внутренних состояний, П - программа.
     Если машина, начав работу с некоторым словом P, записанным на ленте, придет в заключительное состояние, то она называется применимой к этому слову. Результатом ее работы считается слово, записанное на ленте в заключительном состоянии. В противном случае, машина называется не применимой к слову Р.
     Пример. Построим машину Тьюринга, складывающую натуральные числа, записанные в унарной системе счисления (т.е. записанные при помощи одного символа |. Например 5=|||||.).
     Решение. Рассмотрим алфавит А = {|, +, Λ}.
     Машина определяется следующей программой:

 q1q2q3
||q1+1Λq3-1|q3-1
+|q1+1  
ΛΛq2-1 Λq0+1

     Выпишем последовательно возникающие при работе этой машины конфигурации на исходном слове ||+|||, т.е. 2+3. Здесь при записи конфигурации будем использовать следующее соглашение: состояние, в котором находится машина, записывается в круглых скобках справа за обозреваемой буквой.
         0) ...Λ|(q1)|+|||Λ...
         1) ...Λ||(q1)+|||Λ...
         2) ...Λ||+(q1)|||Λ...
         3) ...Λ||||(q1)||Λ...
         4) ...Λ|||||(q1)|Λ...
         5) ...Λ||||||(q1)Λ...
         6) ...Λ||||||Λ(q1)...
         7) ...Λ||||||(q2)Λ...
         8) ...Λ||||||(q3)Λ...
         9) ...Λ||||(q3)|Λ...
         10) ...Λ|||(q3)||Λ...
         11) ...Λ||(q3)|||Λ...
         12) ...Λ|(q3)||||Λ...
         13) ...Λ(q3)|||||Λ...
         14) ...Λ|(q0)||||Λ...
     Пример. Построить машину Тьюринга, удваивающую натуральные числа, записанные в унарной системе счисления.
     Решение. Искомую машину построим в алфавите A={|, α, Λ}.
     Программа такой машины может выглядеть так:

 q1q2q3
|αq1+1|q2-1|q3+1
α |q3+1 
ΛΛq2-1Λq0+1|q2-1

     Применим полученную машину к слову ||.
         0) ...Λ|(q1)|+...
         1) ...Λα|(q1)Λ...
         2) ...ΛααΛ(q1)...
         3) ...Λαα(q2)Λ...
         4) ...Λα|Λ(q3)...
         5) ...Λα|(q2)|Λ...
         6) ...Λα|(q2)|Λ...
         7) ...Λα(q2)||Λ...
         8) ...Λ|(q3)||Λ...
         9) ...Λ|(q2)|||Λ...
         10) ...Λ|(q2)|||Λ...
         11) ...Λ(q2)||||Λ...
         12) ...Λ|(q0)|||Λ...
     Введение новой буквы α и замена исходных | на α позволяет различить исходные | и новые (приписанные) |. Состояние q1 обеспечивает замену | на α, состояние q2 обеспечивает поиск α, предназначенных для замены на |, и останов машины в случае, когда α не обнаружено, q3 обеспечивает дописывание | в случае, когда произошла замена α на |.

@ 2010 - 2017 tablica-istinnosti.ru Рейтинг@Mail.ru