Машина Тьюринга — различия между версиями

Версия 07:41, 8 декабря 2005

Неформально, Машина Тьюринга (далее МТ) представляет собой автомат с конечным числом состояний и неограниченной памятью, представленной набором одной или более лент, бесконечных в обоих направлениях. Ленты поделены на соответственно бесконечное число ячеек, и на каждой ленте выделена стартовая (нулевая) ячейка. В каждой ячейке может быть записан только один символ из некоторого конечного алфавита , где предусмотрен символ «*» для обозначения пустой ячейки.

На каждой ленте имеется головка чтения-записи, и все они подсоединены к «управляющему модулю» МТ — автомату с конечным множеством состояний .

Имеется выделенное стартовое состояние (например, «START») и состояние (или набор состояний) завершения (например «STOP»).

Перед запуском МТ находится в состоянии «START», а все головки позиционированы на нулевые ячейки соответствующих лент. На каждом шаге все головки считывают информацию из своих текущих ячеек и посылают ее управляющему модулю МТ. В зависимости от этих символов и собственного состояния управляющий модуль производит следующие операции:

1. Посылает каждой головке символ для записи в текущую ячейку каждой ленты;
2. Посылает каждой головке одну из команд «LEFT»,"RIGHT","STAY";
3. Выполняет переход в новое состояние (которое, впрочем, может совпадать с предыдущим).

Теперь то же самое более формально.

Машина Тьюринга это набор , где

k

натуральное число,

конечные множества входного алфавита и состояний соответственно,

символ-пробел,

выделенные состояния,

произвольные отображения:

• (задает новое состояние);
• (задает символы для записи на ленты);
• (определяет, как двигать головки).

Удобно считать, что алфавит содержит кроме «пробела» («*») два выделенных символа, «0» и «1» (Обычно вовсе ограничиваются ).

Под входом для МТ подразумевается набор из k слов (k-кортеж слов из ), записанных на k лентах начиная с нулевых позиций. Обычно, на входные данные записывают только на первую ленту, и под входом x подразумевают k-кортеж .

{\it Результатом} работы МТ на некоем входе является также k-кортеж слов из , оставшихся на лентах. Для простоты также удобно считать, что результатом является только слово на последней ленте, а все остальное — просто мусор.

Также считается, что входное слово не содержит пробелов — действительно, иначе было бы невозможно определить, где кончается входное слово (Можно конечно разрешить пробелы, но тогда придется зарезервировать еще один символ — «конец ввода»).

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

• Недетерминированная машина Тьюринга
• Вероятностная машина Тьюринга

Примеры

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

def execute_MT(MT,Tape):
    k=MT["k"]
    T=MT["program"]
    Tape=["*"]+Tape[:]
    configuration={"state":MT["start"], "position":1, "tape": Tape}
    history=[configuration]
    step=0
    while 1:
       step=step+1
       #if we reach the end of the tape --- enlarge it
       if configuration["position"]>=len(configuration["tape"]):
           configuration["tape"].append("*")
 
       #the symbol we are looking at
       symbol=configuration["tape"][configuration["position"]]
 
       #perform transition 
       key=(configuration["state"],(symbol)) 
       action=T[key]
 
       # Just cloning entire configuration: (state,head position,tape)
       new_tape=configuration["tape"][:]
       new_configuration=dict(configuration)     
       new_configuration["tape"]=new_tape
       configuration=new_configuration
 
       #changing state       
       configuration["state"]=action[0]
 
       #write new symbol
       symbol=action[1][0]
       configuration["tape"][configuration["position"]]=symbol
 
       #move head
       move=action[1][1]
       if move=="L": configuration["position"]=configuration["position"]-1
       if move=="R": configuration["position"]=configuration["position"]+1
 
       #tracking configuration
       history.append(configuration)
 
       #if stop state - finishing
       if configuration["state"]==MT["stop"] or step>1000:
           break
 
    return history

Он принимает на вход описание машины Тьюринга в виде хэш-таблицы — рассмотрим пример машины тьюринга для задачи удвоения входной строки (алфавит состоит только из «1»). Описание соответствующей МТ:

MT={
 'k': 1,
 'start': 's1',
 'stop': 'q',
 'program': {
 #(Состояние, символы на лентах) -> (новое состояние, (действия по каждой ленте))
  ('s1', ('1')): ('s2', (('*','R'))),
  ('s2', ('1')): ('s2', (('1','R'))),
  ('s2', ('*')): ('s3', (('*','R'))),
  ('s3', ('*')): ('s4', (('1','L'))),
  ('s3', ('1')): ('s3', (('1','R'))),
  ('s4', ('1')): ('s4', (('1','L'))),
  ('s4', ('*')): ('s5', (('*','L'))),
  ('s5', ('1')): ('s5', (('1','L'))),
  ('s5', ('*')): ('s1', (('1','R'))),
  ('s1', ('*')): ('q',  (('*','')))
 }
}  

Обратите также внимание на альтернативное представление машины Тьюринга в виде ориентированных графа, где вершинами являются состояниями, возможные переходы между ними — ребрами, причем начало ребра помечено символом, который должен быть на ленте для активации перехода, а конец ребра помечен символом, который пишется на ленту, и командой перемещения головки («L», «R», «_» ):

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

Например, вот три запуска симулируемой «удваивающей» МТ на строках «1», «11», «111»:

Можно рассмотреть другие примеры МТ:

• Машина Тьюринга:Распознавание строки, с одинаковым количеством 0 и 1
• Машина Тьюринга:Унарное сложение
• Машина Тьюринга:Распознавание четности