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

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

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

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

Машину Тьюринга с 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 - сдвиг без сдвига.

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

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

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

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

Ссылки