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.