Машинно-независимое описание некоторых машинных классов сложности

Дано единое машинно-независимое описание большого числа классов функций, вычислимых на машинах Тьюринга с ограниченными памятью и временем. Пусть $S$ и $T$ – классы неубывающих функций, удовлетворяющих некоторым простым условиям. Доказано, что класс функций, вычислимых на машинах Тьюринга с памятью, ограниченной функцией из $S$ за время, ограниченное функцией из $T$, совпадает с классом функций, получаемых из некоторых простых исходных функций посредством явных преобразований, суперпозиции и рекурсии вида $f'(x,0)=g(x)$, $f'(x,y+1)=h(x,f'(x,y))$, $|f'(x,y)|\leq s(|x|)$, $f(x,y)=f'(x,t(x))$, где $s\in S$, $t\in T$, $|x|$ – длина двоичного представления числа $x$. Также получены аналогичные описания классов функций, вычислимых с ограниченной памятью и классов функций, вычислимых с ограниченным временем. Библ. – 5 назв.