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

Многодорожечная машина Тьюринга — это особый тип многоленточной машины Тьюринга .

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

Формальное определение

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

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

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

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

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

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

• $M\subseteq M'$

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

• $M'\subseteq M$

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

$M=\langle Q,\Sigma \times {B},\Gamma \times \Gamma ,\delta ',q_{0},F\rangle$ с функцией перехода $\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.