Однозначная машина Тьюринга - Unambiguous Turing machine
В теоретическая информатика, а Машина Тьюринга теоретическая машина, которая используется в мысленные эксперименты изучить возможности и ограничения компьютеров. Однозначная машина Тьюринга - это особый вид недетерминированная машина Тьюринга, который в некотором смысле похож на детерминированную машину Тьюринга.
Формальное определение
А недетерминированная машина Тьюринга представлен формально 6-кратный, , как объяснено на странице недетерминированная машина Тьюринга.An однозначная машина Тьюринга - недетерминированная машина Тьюринга такая, что для всех входных ш = а1а2 ... ап, существует не более одной последовательности конфигураций c0,c1, ..., cм со следующими условиями:
- c0 это начальная конфигурация с вводом ш
- cя+1 является преемником cя и
- cм это принимающая конфигурация.
Другими словами, если ш принимается M, есть ровно одно принимающее вычисление.
Выразительность
(Детерминированная) машина Тьюринга - это однозначная машина Тьюринга. Действительно, для каждого входа возможно ровно одно вычисление.
С одной стороны, однозначная машина Тьюринга обладает такой же выразительностью, что и машина Тьюринга. В самом деле, они представляют собой подмножество недетерминированных машин Тьюринга, которые обладают такой же выразительностью, как машины Тьюринга.
С другой стороны, однозначное недетерминированное полиномиальное время считается менее выразительным, чем недетерминированное полиномиальное время.
Рекомендации
Лейн А. Хемаспандра и Йорг Роте, Однозначные вычисления: булевы иерархии и разреженные полные множества по Тьюрингу, SIAM J. Comput., 26 (3), 634–653