Поляков Е. А.
О типах сходства и рекурсивного изоморфизма частично рекурсивных функций
Polyakov E. A.
On resemblance and recursive isomorphism types of partial recursive functions

Доказано, что тип сходства разнозначной функции, принимающей $n\ge 1$ значений, состоит из $P(n)=\sum\limits_{i=0}^{n}D(n-i)D(i)$ типов рекурсивного изоморфизма, где $D(n)$ --- число разбиений числа $n$ $(D(0)=1)$. Также показно, что если частично рекурсивная функция $\alpha $ отлична от пустой функции и функции-константы и ее тип сходства состоит из одного типа рекурсивного изоморфизма, то $\alpha $ не имеет рекурсивных доопределений.

Полный текст статьи / Full texts:

• PDF file (308 KB)
• PostScript file (580 KB)