О типах сходства и рекурсивного изоморфизма частично рекурсивных функций

Поляков Е.А.

Доказано, что тип сходства разнозначной функции, принимающей значений, состоит из типов рекурсивного изоморфизма, где – число разбиений числа . Также показно, что если частично рекурсивная функция отлична от пустой функции и функции-константы и ее тип сходства состоит из одного типа рекурсивного изоморфизма, то не имеет рекурсивных доопределений.