Однозначная машина Тьюринга - Unambiguous Turing machine

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

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

Недетерминированная машина Тьюринга представлена формально в 6-кортежа , как объяснено в странице недетерминированной машины Тьюринга . Однозначна машина Тьюринга не является детерминированной машиной Тьюринга таким образом, что, для каждого входа ш = с _{1 2} ... в _п , существует не более одной последовательности конфигураций гр ₀ , с ₁ , ..., гр _м с следующие условия: ${\ Displaystyle M = (Q, \ Sigma, \ iota, \ sqcup, A, \ delta)}$

1. c ₀ - начальная конфигурация со входом w
2. c _{i +1} является преемником c _i и
3. c _m - принимающая конфигурация.

Другими словами, если w принимается M , есть ровно одно принимающее вычисление.

Выразительность

Каждая детерминированная машина Тьюринга является однозначной машиной Тьюринга, поскольку для каждого входа возможно ровно одно вычисление. Однозначные машины Тьюринга обладают той же выразительностью, что и машины Тьюринга. Они представляют собой подмножество недетерминированных машин Тьюринга, которые обладают той же выразительностью, что и машины Тьюринга.

С другой стороны, однозначное недетерминированное полиномиальное время считается строго менее выразительным, чем (потенциально неоднозначное) недетерминированное полиномиальное время .

Рекомендации

Лейн А. Хемаспандра и Йорг Роте, Однозначные вычисления: булевы иерархии и разреженные полные по Тьюрингу множества , SIAM J. Comput., 26 (3), 634–653