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

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

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

Недетерминированная машина Тьюринга формально представляется 6-кортежом , $M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )$, как объяснено на странице «Недетерминированная машина Тьюринга» .Однозначная машина Тьюринга — это недетерминированная машина Тьюринга, такая, что для каждого входного сигнала $w=a_{1},a_{2},...,a_{n}$, существует не более одной последовательности конфигураций $c_{0},c_{1},...,c_{m}$ со следующими условиями:

1. $c_{0}$ это начальная конфигурация с вводом $w$
2. $c_{i+1}$ является преемником $c_{i}$ и
3. $c_{m}$ является принимающей конфигурацией.

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

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

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

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

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

Ссылки

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