Beschränkte Maschinen

Für Funktionen t, s : $ \mathbb {N}$$ \to$$ \mathbb {N}$:

Die Maschine M ist t-zeitbeschränkt (bzw. s-platzbeschränkt),

falls jede akzeptierende Rechnung für eine Eingabe der Länge n

aus höchstens t(n) Schritten besteht

(bzw. nie mehr als s(n) Zellen des Arbeitsbandes benutzt).



Johannes Waldmann 2005-01-25