|
Записки научных семинаров ЛОМИ, 1979, том 88, страницы 176–185
(Mi znsl3111)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Машинно-независимое описание некоторых машинных классов сложности
С. В. Пахомов
Аннотация:
Дано единое машинно-независимое описание большого числа классов функций, вычислимых на машинах Тьюринга с ограниченными памятью и временем. Пусть $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 назв.
Образец цитирования:
С. В. Пахомов, “Машинно-независимое описание некоторых машинных классов сложности”, Исследования по конструктивной математике и математической логике. VIII, Зап. научн. сем. ЛОМИ, 88, Изд-во «Наука», Ленинград. отд., Л., 1979, 176–185; J. Soviet Math., 20:4 (1982), 2358–2363
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl3111 https://www.mathnet.ru/rus/znsl/v88/p176
|
Статистика просмотров: |
Страница аннотации: | 134 | PDF полного текста: | 39 |
|