Многолента машина Тьюринга - Multitape Turing machine

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

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

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

Машину Тьюринга с k-лентой можно описать как кортеж из 6 ${\displaystyle M=\langle Q,\Gamma ,s,b,F,\delta \rangle }$ куда:

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

Двухъярусная машина Тьюринга

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

Смотрите также

• Машина Тьюринга
• Универсальная машина Тьюринга
• Переменная машина Тьюринга
• Вероятностная машина Тьюринга
• Эквиваленты машины Тьюринга

Рекомендации

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