RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Зап. научн. сем. ПОМИ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Зап. научн. сем. ЛОМИ, 1979, том 88, страницы 176–185 (Mi znsl3111)  

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

С. В. Пахомов


Аннотация: Дано единое машинно-независимое описание большого числа классов функций, вычислимых на машинах Тьюринга с ограниченными памятью и временем. Пусть $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 назв.

Полный текст: PDF файл (497 kB)

Англоязычная версия:
Journal of Soviet Mathematics, 1982, 20:4, 2358–2363

Реферативные базы данных:

УДК: 510.52

Образец цитирования: С. В. Пахомов, “Машинно-независимое описание некоторых машинных классов сложности”, Исследования по конструктивной математике и математической логике. VIII, Зап. научн. сем. ЛОМИ, 88, Изд-во «Наука», Ленинград. отд., Л., 1979, 176–185; J. Soviet Math., 20:4 (1982), 2358–2363

Цитирование в формате AMSBIB
\RBibitem{Pak79}
\by С.~В.~Пахомов
\paper Машинно-независимое описание некоторых машинных классов сложности
\inbook Исследования по конструктивной математике и математической логике.~VIII
\serial Зап. научн. сем. ЛОМИ
\yr 1979
\vol 88
\pages 176--185
\publ Изд-во «Наука», Ленинград. отд.
\publaddr Л.
\mathnet{http://mi.mathnet.ru/znsl3111}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=556228}
\zmath{https://zbmath.org/?q=an:0429.03019|0493.03014}
\transl
\jour J. Soviet Math.
\yr 1982
\vol 20
\issue 4
\pages 2358--2363
\crossref{https://doi.org/10.1007/BF01629446}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/znsl3111
  • http://mi.mathnet.ru/rus/znsl/v88/p176

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Записки научных семинаров ПОМИ
    Просмотров:
    Эта страница:97
    Полный текст:31
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020