Персональные инструменты
 

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

Материал из CustisWiki

Перейти к: навигация, поиск
м (1 версия)
м (обновление данных)
Строка 4: Строка 4:
 
Ленты поделены на соответственно бесконечное число ячеек, и на каждой ленте
 
Ленты поделены на соответственно бесконечное число ячеек, и на каждой ленте
 
выделена стартовая (нулевая) ячейка. В каждой ячейке может быть записан
 
выделена стартовая (нулевая) ячейка. В каждой ячейке может быть записан
только один символ из некоторого конечного алфавита <math>\Sigma</math>, где
+
только один символ из некоторого конечного алфавита <m>\Sigma</m>, где
 
предусмотрен символ «*» для обозначения пустой ячейки.
 
предусмотрен символ «*» для обозначения пустой ячейки.
  
 
На каждой ленте имеется головка чтения-записи, и все они
 
На каждой ленте имеется головка чтения-записи, и все они
подсоединены к «управляющему модулю» МТ — автомату с конечным множеством состояний <math>\Gamma</math>.
+
подсоединены к «управляющему модулю» МТ — автомату с конечным множеством состояний <m>\Gamma</m>.
  
 
Имеется выделенное стартовое состояние (например, «START») и состояние (или набор состояний) завершения (например «STOP»).
 
Имеется выделенное стартовое состояние (например, «START») и состояние (или набор состояний) завершения (например «STOP»).
Строка 25: Строка 25:
 
      
 
      
 
''Машина Тьюринга'' это набор  
 
''Машина Тьюринга'' это набор  
<math>T= \langle k,\Sigma,\Gamma,\alpha,\beta,\gamma \rangle</math>,
+
<m>T= \langle k,\Sigma,\Gamma,\alpha,\beta,\gamma \rangle</m>,
 
где
 
где
  
 
;k: натуральное число,
 
;k: натуральное число,
;<math>\Sigma,\Gamma</math>: конечные множества входного алфавита и состояний соответственно,
+
;<m>\Sigma,\Gamma</m>: конечные множества входного алфавита и состояний соответственно,
;<math>\star \in \Sigma</math>: символ-пробел,  
+
;<m>\star \in \Sigma</m>: символ-пробел,  
;<math>START,STOP \in \Gamma</math>: выделенные состояния,
+
;<m>START,STOP \in \Gamma</m>: выделенные состояния,
;<math>\alpha,\beta,\gamma</math>: произвольные отображения:
+
;<m>\alpha,\beta,\gamma</m>: произвольные отображения:
:*<math>\alpha: \Gamma \times \Sigma^k \rightarrow \Gamma  </math> (задает новое состояние);
+
:*<m>\alpha: \Gamma \times \Sigma^k \rightarrow \Gamma  </m> (задает новое состояние);
:*<math>\beta : \Gamma \times \Sigma^k \rightarrow \Sigma^k  </math> (задает символы для записи на ленты);
+
:*<m>\beta : \Gamma \times \Sigma^k \rightarrow \Sigma^k  </m> (задает символы для записи на ленты);
:*<math>\gamma: \Gamma \times \Sigma^k \rightarrow \{-1,0,1\}^k </math> (определяет, как двигать головки).
+
:*<m>\gamma: \Gamma \times \Sigma^k \rightarrow \{-1,0,1\}^k </m> (определяет, как двигать головки).
  
Удобно считать, что алфавит <math>\Sigma</math> содержит кроме «пробела» («*»)
+
Удобно считать, что алфавит <m>\Sigma</m> содержит кроме «пробела» («*»)
два выделенных символа, «0» и «1» (Обычно вовсе ограничиваются <math>\Sigma \equiv \{\star,0,1\}</math>).
+
два выделенных символа, «0» и «1» (Обычно вовсе ограничиваются <m>\Sigma \equiv \{\star,0,1\}</m>).
  
Под ''входом'' для МТ подразумевается набор из ''k'' слов (''k''-кортеж слов из <math>\Sigma^*</math>),
+
Под ''входом'' для МТ подразумевается набор из ''k'' слов (''k''-кортеж слов из <m>\Sigma^*</m>),
 
записанных на ''k'' лентах начиная с нулевых позиций.
 
записанных на ''k'' лентах начиная с нулевых позиций.
 
Обычно, на входные данные записывают только на первую ленту, и под входом ''x''
 
Обычно, на входные данные записывают только на первую ленту, и под входом ''x''
подразумевают ''k''-кортеж <math>\langle x,0,\ldots,0 \rangle</math>.
+
подразумевают ''k''-кортеж <m>\langle x,0,\ldots,0 \rangle</m>.
  
 
{\it Результатом} работы МТ на некоем входе является также
 
{\it Результатом} работы МТ на некоем входе является также
''k''-кортеж слов из <math>\Sigma^*</math>, оставшихся на лентах. Для простоты
+
''k''-кортеж слов из <m>\Sigma^*</m>, оставшихся на лентах. Для простоты
 
также удобно считать, что ''результатом'' является только слово на последней
 
также удобно считать, что ''результатом'' является только слово на последней
 
ленте, а все остальное — просто мусор.
 
ленте, а все остальное — просто мусор.

Версия 18:34, 22 октября 2008

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

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

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

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

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

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

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

k
натуральное число,
конечные множества входного алфавита и состояний соответственно,
символ-пробел,
выделенные состояния,
произвольные отображения:
  • (задает новое состояние);
  • (задает символы для записи на ленты);
  • (определяет, как двигать головки).

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

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

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

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

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


Примеры

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

def execute_MT(MT,input):
    T=MT["program"]
    tape=["*"]+input
    state=MT["start"]
    position=1
    history=[{"state":state, "position":position, "tape": []+tape}]
    step=0
    while 1:
       step=step+1
       if position>=len(tape):
           tape.append("*")
       symbol_under_head=tape[position]
       action=T[(state,(symbol_under_head))]
       state=action[0]
       symbol_to_write=action[1][0]
       tape[position]=symbol_to_write
       move=action[1][1]
       if move=="L": position=position-1
       if move=="R": position=position+1
       history.append({"state":state, "position":position, "tape": []+tape})
       if state==MT["stop"] or step>1000:
           break
    return history


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

Таблица МТ в виде Python-структуры для вышеприведенного симулятора:

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», «_» ):

[svg]

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

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


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


Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».

Репликация: База Знаний «Заказных Информ Систем» → «Машина Тьюринга»