Univerzální Turingův stroj
25/45
Myšlenka: Univerzální TS může odsimulovat libovolný DTS
Ilustrace:
Univerzální TS U
Zakódovaný M, d(M)
Vstupní řet. w
…
D
Pozn.: Univerzální
TS přečte zakódování TS M
a vstupní řetězec w na pásce a pak odsimuluje přechody, které by prováděl TS M se vstupním řetězcem
w.