Мульти-лента машина Тьюринга представляет собой вариант машины Тьюринга , которая использует несколько лент. У каждой ленты своя головка для чтения и записи. Первоначально ввод появляется на ленте 1, а остальные начинаются пустыми. [1]
Эта модель интуитивно кажется намного более мощной, чем модель с одной лентой, но любую машину с несколькими лентами - независимо от того, сколько лент - можно смоделировать с помощью машины с одной лентой, используя только квадратично большее время вычислений. [2] Таким образом, многоленточные машины не могут вычислять больше функций, чем однопленочные машины, [3] и ни на один из устойчивых классов сложности (например, полиномиальное время ) не влияет изменение между однопленочными и многоленточными машинами .
Формальное определение [ править ]
Машину Тьюринга с k-лентой можно описать как кортеж из 6 элементов, в котором:
- конечный набор состояний
- конечный набор ленточного алфавита
- это начальное состояние
- это пустой символ
- это набор конечных или принимающих состояний
- - это частичная функция, называемая функцией перехода, где k - количество лент, L - сдвиг влево, R - сдвиг вправо, а S - сдвиг без сдвига.
Двухъярусная машина Тьюринга [ править ]
Двухстековые машины Тьюринга имеют вход только для чтения и две ленты хранения. Если головка перемещается влево на любой из лент, на этой ленте печатается бланк, но можно напечатать один символ из «библиотеки».
См. Также [ править ]
- Машина Тьюринга
- Универсальная машина Тьюринга
- Переменная машина Тьюринга
- Вероятностная машина Тьюринга
- Эквиваленты машины Тьюринга
Ссылки [ править ]
- ^ Сипсер, Майкл (2005). Введение в теорию вычислений . Thomson Course Technology. п. 148. ISBN 0-534-95097-3.
- ^ Papadimitriou, Christos (1994). Вычислительная сложность . Эддисон-Уэсли. п. 53 . ISBN 0-201-53082-1.
- ^ Мартин, Джон (2010). Введение в языки и теорию вычислений . Макгроу Хилл. С. 243–246. ISBN 978-0071289429.