TS s oboustranně nekonečnou páskou
22/45
Myšlenka: Turingův stroj s páskou, která je nekonečná směrem doleva i doprava
Ilustrace:
p
a1
x1
y1
…
…
Tvrzení: Pro každý TS M existuje
ekvivalentní TS s oboustranně
nekonečnou páskou M.
Důkaz: Viz. str. 673 v knize [Meduna: Automata and Languages]