|
Записки научных семинаров ЛОМИ, 1979, том 88, страницы 30–46
(Mi znsl3100)
|
|
|
|
Эта публикация цитируется в 12 научных статьях (всего в 12 статьях)
Машинное описание и иерархия начальных классов Гжегорчика
А. П. Бельтюков
Аннотация:
Строится тип абстрактных вычислительных машин и мера сложности вычислений на этих машинах, естественным образом связанные с иерархией Гжегорчика. Для определения этого типа машин не требуется рекурсивного построения, присутствующего в исходном определении классов Гжегорчика. Все классы Гжегорчика $\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 назв.
Образец цитирования:
А. П. Бельтюков, “Машинное описание и иерархия начальных классов Гжегорчика”, Исследования по конструктивной математике и математической логике. VIII, Зап. научн. сем. ЛОМИ, 88, Изд-во «Наука», Ленинград. отд., Л., 1979, 30–46; J. Soviet Math., 20:4 (1982), 2280–2289
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl3100 https://www.mathnet.ru/rus/znsl/v88/p30
|
Статистика просмотров: |
Страница аннотации: | 366 | PDF полного текста: | 140 |
|