Многолента машина Тьюринга - 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 substeq Q}$ это набор конечных или принимающих состояний
• ${ displaystyle delta: Q times Gamma ^ {k} rightarrow Q times ( Gamma times {L, R, S }) ^ {k}}$ - частичная функция, называемая функцией перехода, где k - количество лент, L - сдвиг влево, R - сдвиг вправо, а S - сдвиг без сдвига.

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

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

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

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

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