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

редактировать

Машины Тьюринга
Машина
Эквиваленты машины Тьюринга Примеры машины Тьюринга Галерея машин Тьюринга
Варианты
Переменная машина Тьюринга Дифференцируемый нейронный компьютер Недетерминированная машина Тьюринга Квантовая машина Тьюринга Машина Пост-Тьюринга Вероятностная машина Тьюринга Машина Тьюринга только для чтения Право движущиеся машины Тьюринга только для чтения Многолента машина Тьюринга Многодорожечная машина Тьюринга Симметричная машина Тьюринга Общая машина Тьюринга Однозначная машина Тьюринга Универсальная машина Тьюринга Зенон машина
Наука
Алан Тьюринг Категория: машина Тьюринга
v т е

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

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

Содержание

1 Формальное определение
2 Двухъярусная машина Тьюринга
3 См. Также
4 ссылки

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

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

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

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

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

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

Ссылки

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