Машинное описание и иерархия начальных классов Гжегорчика

Строится тип абстрактных вычислительных машин и мера сложности вычислений на этих машинах, естественным образом связанные с иерархией Гжегорчика. Для определения этого типа машин не требуется рекурсивного построения, присутствующего в исходном определении классов Гжегорчика. Все классы Гжегорчика $\mathscr E_*^n$ при $n=0,1,2,3,\dots$ оказываются сложностными классами для указанного типа машин и указанной меры сложности. На основании подобных машин получается также сложностное описание класса предикатов, рудиментарных по Смульяну. С помощью исследуемых машин доказывается совпадение по предикатам с $\mathscr E_*^0$ некоторых подклассов $\mathscr E^1$, основанных на ограниченной рекурсии. Доказано отсутствие у класса одноместных функций из $\mathscr E^0$ и у некоторых близких классов конечного базиса относительно суперпозиции. Доказано, что равенство $\mathscr E_*^1=\mathscr E_*^2$ влечет равенство $\mathscr E_*^0=\mathscr E_*^1$. Библ. – 14 назв.