Für Funktionen t, s : :
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).