Machine-independent description of some machine complexity classes
Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part VIII, Tome 88 (1979), pp. 176-185
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
@article{ZNSL_1979_88_a12,
author = {S. V. Pakhomov},
title = {Machine-independent description of some machine complexity classes},
journal = {Zapiski Nauchnykh Seminarov POMI},
pages = {176--185},
publisher = {mathdoc},
volume = {88},
year = {1979},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZNSL_1979_88_a12/}
}
S. V. Pakhomov. Machine-independent description of some machine complexity classes. Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part VIII, Tome 88 (1979), pp. 176-185. http://geodesic.mathdoc.fr/item/ZNSL_1979_88_a12/