Доказательства принадлежности рефал-5 функций некоторым подклассам FP-SPACE
Keywords:
машина Тьюринга, полиномиальное число шагов, рефал-5, подклассы класса FP-SPACE, подклассы класса FP
Abstract
Вводятся иерархии классов сложности функций как из FP, так и из FP-SPACE. В статье доказывается теорема о замкнутости классов функций этих иерархий, а также классов функций FP||LIN-SPACE и FP||QLIN-SPACE и классов предикатов P||LIN-SPACE и P||QLIN-SPACE относительно определения рефал-5 функций с ограниченными сверху числом рекурсивных вызовов и величиной использованной памяти. С. 3-8.
Published
2014-01-23
How to Cite
Косовский, Н. К. (2014). Доказательства принадлежности рефал-5 функций некоторым подклассам FP-SPACE. Computer Tools in Education, (3). Retrieved from http://cte.eltech.ru/ojs/index.php/kio/article/view/1345
Issue
Section
Articles
This work is licensed under a Creative Commons Attribution 4.0 International License.
