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

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

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

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

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

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

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

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

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

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

Ссылки

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