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

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

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

А недетерминированная машина Тьюринга представлен формально 6-кратный, , как объяснено на странице недетерминированная машина Тьюринга.An однозначная машина Тьюринга - недетерминированная машина Тьюринга такая, что для всех входных ш = а1а2 ... ап, существует не более одной последовательности конфигураций c0,c1, ..., cм со следующими условиями:

  1. c0 это начальная конфигурация с вводом ш
  2. cя+1 является преемником cя и
  3. cм это принимающая конфигурация.

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

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

(Детерминированная) машина Тьюринга - это однозначная машина Тьюринга. Действительно, для каждого входа возможно ровно одно вычисление.

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

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

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

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