RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. LOMI, 1979 Volume 88, Pages 176–185 (Mi znsl3111)

This article is cited in 1 paper

Machine-independent description of some machine complexity classes

S. V. Pakhomov


Abstract: A uniform machine-independent description is given for a large number of classes of functions computable by Turing machines within, bounded space and time. Let $S$ and $T$ be the classes of nondecreasing functions satisfying conditions (S1)–(S3), (T1), (T2), (ST1)–(ST3). It is proved that the class of functions computable by a Turing machine within space bounded by a function belonging to $S$ and within time bounded by a function belonging to $T$ is equal to the class of functions obtainable from some simple initial functions by means of explicit transformation, substitution and recursion of the type ($*$) where $s\in S$, $t\in T$. Analogous descriptions of classes of functions computable within bounded space and classes of functions computable within bounded time are also presented.

UDC: 510.52


 English version:
Journal of Soviet Mathematics, 1982, 20:4, 2358–2363

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025