2.4. Idő- és tárkorlát

A T Turing-gép t(n) időkorlátos, ha n hosszú inputon legfeljebb t(n) lépést tesz. TIME(t(n)) azon nyelvek halmaza, melyek felismerhetőek egy O(t(n)) időkorlátos Turing-géppel. A T Turing-gép s(n) tárkorlátos, ha n hosszú inputon legfeljebb s(n) mezőt használ a munkaszalagokon. SPACE(s(n)) azon nyelvek halmaza, melyek felismerhetőek egy O(s(n)) tárkorlátos Turing-géppel. Ezek alapján definiálhatjuk a következő halmazokat:

2.. egyenlet -


2.. egyenlet -


2.. egyenlet -