Многоленточная машина Тьюринга

Многоленточная машина Тьюринга — это вариант машины Тьюринга , в котором используется несколько лент. Каждая лента имеет собственную головку для чтения и записи. Первоначально входные данные появляются на ленте 1, а остальные начинаются пустыми. ^[1]

Эта модель интуитивно кажется гораздо более мощной, чем модель с одной лентой, но любая машина с несколькими лентами — независимо от того, сколько лент — может быть смоделирована с помощью машины с одной лентой, используя только квадратично большее время вычислений. ^[2] Таким образом, многоленточные машины не могут вычислять больше функций, чем одноленточные машины. ^[3] и ни один из классов устойчивой сложности (например, полиномиальное время ) не зависит от перехода между одноленточными и многоленточными машинами.

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

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

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

А $k$ -ленточная машина Тьюринга $M$ рассчитывается следующим образом. Изначально, $M$ получает свои входные данные $w=w_{1}w_{2}...w_{n}\in \Sigma ^{*}$ в крайнем левом углу $n$ позиции первой ленты, остальная часть первой ленты, а также другие ленты пусты (т.е. заполнены пустыми символами). Все головки начинаются с крайнего левого положения лент. Один раз $M$ начался, вычисление продолжается по правилам, описанным функцией перехода. Вычисления продолжаются до тех пор, пока не перейдут в состояния принятия, после чего они останавливаются.

Двухстековая машина Тьюринга

Двухстековые машины Тьюринга имеют вход только для чтения и две ленты хранения. Если головка перемещается влево на любой ленте, на этой ленте печатается пробел, но можно напечатать один символ из «библиотеки».

См. также

Ссылки

^ Сипсер, Майкл (2005). Введение в теорию вычислений . Технология курса Томсона. п. 148. ИСБН 0-534-95097-3 .
^ Пападимитриу, Христос (1994). Вычислительная сложность . Аддисон-Уэсли. п. 53 . ISBN 0-201-53082-1 .
^ Мартин, Джон (2010). Введение в языки и теорию вычислений . МакГроу Хилл. стр. 243–246. ISBN 978-0071289429 .

[1] Сипсер, Майкл (2005). Введение в теорию вычислений . Технология курса Томсона. п. 148. ИСБН 0-534-95097-3 .

[2] Пападимитриу, Христос (1994). Вычислительная сложность . Аддисон-Уэсли. п. 53 . ISBN 0-201-53082-1 .

[3] Мартин, Джон (2010). Введение в языки и теорию вычислений . МакГроу Хилл. стр. 243–246. ISBN 978-0071289429 .

[1]

[2]

[3]