Машина переменного Тьюринга
-
Определение и свойства чередующейся машины Тьюринга
- Чередующаяся машина Тьюринга — это машина, которая может переходить между экзистенциальным и универсальным состояниями.
- Машина может быть запущена в любом состоянии и может принимать решения о ветвлении на основе количественных переменных.
- Машина принимает решение, если результирующая формула истинна, и отклоняет в противном случае.
-
Классы сложности и их связь с чередующейся машиной Тьюринга
- Определены классы сложности AP, APSPACE, AEXPTIME, которые аналогичны P, PSPACE, EXPTIME, но с учетом ресурсов банкомата.
- Чандра, Козен и Стокмейер доказали теоремы, связывающие эти классы и иерархию чередования.
-
Ограниченное чередование и сворачивающиеся классы
- Определены машины с ограниченным чередованием, которые переключаются не более k-1 раз, и иерархические системы, в которых каждый уровень является частью иерархии.
- Логарифмическая пространственная иерархия сворачивается до первого уровня, когда функция f является конструктивной.
-
Особые случаи и рекомендации
- Чередующаяся машина Тьюринга может решить все задачи в классах ΣkP и ΠkP, а также все задачи в логарифмической иерархии.
- Для дальнейшего чтения рекомендуется обратиться к соответствующим разделам книги.
Полный текст статьи: