Hoofdstuk 10: Other models of Turing
machines
1 Equivalentie van verschillende klassen automaten
Stel 2 klassen automaten 𝐶1 en 𝐶2 .
• 𝐶1 is minstens zo krachtig als 𝐶2 indien voor elke automaat 𝑀2 in 𝐶2 er een automaat 𝑀1
bestaat in 𝐶1 zodat 𝐿(𝑀2 ) = 𝐿(𝑀1 ).
• 𝐶1 en 𝐶2 zijn equivalent als het vorige waar is en omgekeerd.
Voorbeeld:
Turing machines are at least as powerful as push-down automata. But they are not equivalent.
2 Simulatie
Om equivalentie van Turing machines mee te bewijzen
Indien voor elke derivation
𝑑0 ⊢ 𝑀𝑑1 ⊢ 𝑀 … ⊢ 𝑀𝑑𝑛 …
Een derivation
∗ ∗ ∗
𝑑̂0 ̂ 𝑑̂1 𝑀
𝑀 ̂… 𝑀̂ 𝑑̂𝑛 …
⊢ ⊢ ⊢
̂ M kan simuleren.
Bestaat, zeggen we dat 𝑀
̂.
M.a.w. er bestaat een mapping van de instanteneous descriptions van M naar 𝑀
3 Andere modellen Turing machines
Stelling:
The class of Turing machines with a stay-option is equivalent to the class of standard Turing
machines.
• Trick: staying is going left, and then changing nothing and going right again.
Stelling:
The class of Turing machines with a multiple tracks is equivalent to the class of standard Turing
machines.
• Trick: We kunnen meerdere tracks zien als 1 track waarbij op die ene track n-tuples staan
indien er n tracks zijn.
• Is dus eigenlijk een standaard Turing machine
1
machines
1 Equivalentie van verschillende klassen automaten
Stel 2 klassen automaten 𝐶1 en 𝐶2 .
• 𝐶1 is minstens zo krachtig als 𝐶2 indien voor elke automaat 𝑀2 in 𝐶2 er een automaat 𝑀1
bestaat in 𝐶1 zodat 𝐿(𝑀2 ) = 𝐿(𝑀1 ).
• 𝐶1 en 𝐶2 zijn equivalent als het vorige waar is en omgekeerd.
Voorbeeld:
Turing machines are at least as powerful as push-down automata. But they are not equivalent.
2 Simulatie
Om equivalentie van Turing machines mee te bewijzen
Indien voor elke derivation
𝑑0 ⊢ 𝑀𝑑1 ⊢ 𝑀 … ⊢ 𝑀𝑑𝑛 …
Een derivation
∗ ∗ ∗
𝑑̂0 ̂ 𝑑̂1 𝑀
𝑀 ̂… 𝑀̂ 𝑑̂𝑛 …
⊢ ⊢ ⊢
̂ M kan simuleren.
Bestaat, zeggen we dat 𝑀
̂.
M.a.w. er bestaat een mapping van de instanteneous descriptions van M naar 𝑀
3 Andere modellen Turing machines
Stelling:
The class of Turing machines with a stay-option is equivalent to the class of standard Turing
machines.
• Trick: staying is going left, and then changing nothing and going right again.
Stelling:
The class of Turing machines with a multiple tracks is equivalent to the class of standard Turing
machines.
• Trick: We kunnen meerdere tracks zien als 1 track waarbij op die ene track n-tuples staan
indien er n tracks zijn.
• Is dus eigenlijk een standaard Turing machine
1
