언앰비지터 튜링머신

이론 컴퓨터 과학에서 튜링 기계는 컴퓨터의 능력과 한계를 검사하기 위해 사고 실험에 사용되는 이론 기계다.모호하지 않은 튜링 기계는 특별한 종류의 결정론적 튜링 기계로, 어떤 의미에서는 결정론적 튜링 기계와 유사하다.

형식 정의

비결정론적 튜링 시스템은 비결정론적 튜링 시스템 페이지에 설명된 대로 6-투플, M${\displaystyle }$=${\displaystyle }$(${\displaystyle Q}$, ${\displaystyle \mathrm{\iota }}$,${\displaystyle \iota }$ , ${\displaystyle \bigsqcup }$, ${\displaystyle A}$ ,${\displaystyle \Delta }$) ${\디스플레이$ 스타일 $M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )}$에 의해 공식적으로 표현된다$.$An unambiguous Turing machine is a non-deterministic Turing machine such that, for every input ${\displaystyle w=a_{1},a_{2},...,a_{n}}$, there exists at most one sequence of configurations ${\displaystyle c_{0},c_{1},...,c_{m}}$ with the following conditions:

1. ${\displaystyle c_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$은(는) $입력$이 ${\displaystyle w}$인 초기 구성이다.
2. ${\displaystyle c_{}}$ ${\displaystyle i_{}}$+ ${\displaystyle 1_{}}$ ${\$}은$($는$)$ ${\displaystyle c_{}}$ i {\$displaystyle$ c_${i}$의 후속 제품이며$$
3. ${\displaystyle c_{m}}$허용 가능한 구성이다.

즉, $w{\displaystyle }$ ${\displaystyle w}$이(가) $M{\displaystyle }$ ${\displaystyle M}$에 의해 수락된$$ 경우$,$ 정확히 하나의 수락 계산이 있다.

표현성

모든 결정론적 튜링 기계는 모호하지 않은 튜링 기계로, 각 입력에 대해, 정확히 하나의 계산이 가능하다.모호하지 않은 튜링 기계는 튜링 기계와 같은 표현력을 가지고 있다.그것들은 튜링 기계와 같은 표현성을 가진 결정론적 튜링 기계의 하위 집합체다.

반면 모호하지 않은 비결정론적 다항 시간은 (잠재적으로 모호한) 비결정론적 다항식 시간보다 엄격히 표현력이 떨어지는 것으로 의심된다.

참조

레인 A. Hemaspaandra 및 Jorg Rothe, Unambiguous Computing: 부울 계층 구조 및 희소 튜링 완료 세트, SIAM J. Compute, 26(3), 634–653