Многодорожечная машина Тьюринга

Эта статья может быть слишком технической, чтобы ее могло понять большинство читателей . Пожалуйста, помогите улучшить его, чтобы он был понятен неспециалистам , не удаляя технические детали. ( Июнь 2018 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

В стандартной машине Тьюринга с n-лентой n головок независимо перемещаются по n дорожкам. В n-трековой машине Тьюринга одна головка считывает и записывает все треки одновременно. Позиция ленты в n-трековой машине Тьюринга содержит n символов из алфавита ленты. Он эквивалентен стандартной машине Тьюринга и поэтому принимает в точности рекурсивно перечислимые языки .

Формальное определение [ править ]

Многодорожечная машина Тьюринга с -лентами может быть формально определена как кортеж из 6 , где${\ displaystyle n}$${\displaystyle M=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle }$

• ${\displaystyle Q}$ конечный набор состояний
• ${\displaystyle \Sigma }$конечный набор символов, называемый ленточным алфавитом
• ${\displaystyle \Gamma \in Q}$
• ${\displaystyle q_{0}\in Q}$это начальное состояние
• ${\displaystyle F\subseteq Q}$- это набор конечных или принимающих состояний .
• ${\displaystyle \delta :\left(Q\backslash F\times \Sigma ^{n}\right)\rightarrow \left(Q\times \Sigma ^{n}\times \{L,R\}\right)}$является частичной функцией, называемой функцией перехода .

Иногда также обозначается как , где .${\displaystyle \delta \left(Q_{i},[x_{1},x_{2}...x_{n}]\right)=(Q_{j},[y_{1},y_{2}...y_{n}],d)}$${\displaystyle d\in \{L,R\}}$

Недетерминированный вариант может быть определен путем замены функции перехода на переходной связи .${\displaystyle \delta }$ ${\displaystyle \delta \subseteq \left(Q\backslash F\times \Sigma ^{n}\right)\times \left(Q\times \Sigma ^{n}\times \{L,R\}\right)}$

Доказательство эквивалентности стандартной машине Тьюринга [ править ]

Это докажет, что двухдорожечная машина Тьюринга эквивалентна стандартной машине Тьюринга. Это можно обобщить на n-трековую машину Тьюринга. Пусть L - рекурсивно перечислимый язык. Пусть M = стандартная машина Тьюринга, которая принимает L. Пусть M 'двухдорожечная машина Тьюринга. Чтобы доказать M = M ', необходимо показать, что M M' и M ' M${\displaystyle \langle Q,\Sigma ,\Gamma ,\delta ,q_{0},F\rangle }$${\displaystyle \subseteq }$${\displaystyle \subseteq }$

• ${\displaystyle M\subseteq M'}$

Если все треки, кроме первого, игнорируются, то M и M 'явно эквивалентны.

• ${\displaystyle M'\subseteq M}$

Ленточный алфавит однодорожечной машины Тьюринга, эквивалентной двухдорожечной машине Тьюринга, состоит из упорядоченной пары . Входной символ a машины Тьюринга M 'может быть идентифицирован как упорядоченная пара [x, y] машины Тьюринга M. Однодорожечная машина Тьюринга:

M = с переходной функцией${\displaystyle \langle Q,\Sigma \times {B},\Gamma \times \Gamma ,\delta ',q_{0},F\rangle }$${\displaystyle \delta \left(q_{i},[x_{1},x_{2}]\right)=\delta '\left(q_{i},[x_{1},x_{2}]\right)}$

Эта машина также принимает L.

Ссылки [ править ]

• Томас А. Судкамп (2006). Языки и машины, третье издание. Эддисон-Уэсли. ISBN  0-321-32221-5 . Глава 8.6: Многоленточные машины: стр. 269–271