WikiDer > Машина Тьюринга с произвольным доступом
Random-access Turing machine
 | Эта статья нужны дополнительные цитаты для проверка. (Август 2010 г.) (Узнайте, как и когда удалить этот шаблон сообщения) |
В вычислительная сложность, поле Информатика, машины Тьюринга с произвольным доступом являются продолжением Машины Тьюринга раньше говорили о классах небольшой сложности, особенно для классов, использующих логарифмическое время, например DLOGTIME и Логарифмическая иерархия.
Определение
На машине Тьюринга с произвольным доступом есть специальный указатель лента логарифмического пространства, принимающая двоичный словарь. Машина Тьюринга имеет особое состояние, когда двоичное число на указатель ленте 'p', машина Тьюринга запишет на рабочую ленту п-й символ входа.
Это позволяет машине Тьюринга читать любую букву ввода, не тратя времени на перемещение по всему вводу. Это обязательно для классов сложности, использующих время меньше линейного.
Рекомендации
- Н. Иммерман Описательная сложность (1999 Springer), глава 5
| P ≟ NP | Этот теоретическая информатика–Связанная статья является заглушка. Вы можете помочь Википедии расширяя это. |