log space transducer

Einfache Sprache

Def. log space transducer

Ein Logarithmische Platzkomplexität Transduktor ist eine TM mit einem read-only Eingabeband, einem write-only Ausgabeband und einem read-write Arbeitsband. Der Lese-Schreib-Kopf auf dem Ausgabeband kann sich nur nach Links bewegen. Er kann also nicht lesen was er geschrieben hat. Das Arbeitsband ist $O(\log n)$ groß. Ein Logarithmische Platzkomplexität Transduktor $\mathcal M$ berechnet die Funktion $f:\Sigma^* \to \Sigma^*$. Also wenn $\mathcal M$ mit der Eingabe $w$ auf dem Eingabeband akzeptiert, steht die Zeichenkette $f(w)$ auf dem Ausgabeband. Beachte das $f$ eine Logarithmische Platzkomplexität berechenbare Funktion ist.