Nur-Lesen Eingabeband Turingmaschine
Einfache Sprache
Def. Nur-Lesen-Eingabeband Turingmaschine
Eine Nur-Lesen-Eingabeband Turingmaschine ist eine TM, die ein Eingabeband und ein Arbeitsband hat, wobei das Eingabeband kann nur gelesen werden.
Beispiel
Man stelle sich einen Computer vor der eine CD-ROM hat, die viel mehr Speicher hat als der Computer.
Benutzt man ROITM in Satz von Savitch, so kann man den Satz auf sublineare Platzkomplexitäten mit $f(n)\geq\log n$ erweitern.