Satz Redundanz zusätzlicher Bänder

Einfache Sprache

Für jede k-Band TM existiert eine äquivalente 1-Band TM, also eine TM die nur ein Band benutzt. Dafür wird jedoch die Komplexität quadriert.

Def. Satz Redundanz zusätzlicher Bänder

Sei $t(n)$ eine Funktion, für die $t(n)\geq n$ gilt. Jede k-Band TM die in $t(n)$ läuft hat ein äquivalent 1-Band TM die in $t^2(n)$ läuft.

TODO BeweisS