В области вычислительной сложности , области информатики , машины Тьюринга с произвольным доступом являются расширением машин Тьюринга, используемых для описания классов небольшой сложности, особенно для классов, использующих логарифмическое время , таких как DLOGTIME и логарифмическая иерархия .
Определение
На машине Тьюринга с произвольным доступом имеется специальная указательная лента в логарифмическом пространстве, принимающая двоичный словарь. Машина Тьюринга имеет особое состояние: когда двоичное число на ленте указателя равно «p», машина Тьюринга записывает на рабочую ленту p- й символ ввода.
Лента указателя позволяет машине Тьюринга читать любую букву ввода, не тратя времени на перемещение по всему вводу. Это обязательно для классов сложности, использующих менее линейное время .
Рекомендации
- Нил Иммерман « Описательная сложность» (1999 Springer), глава 5