Types of resemblance and of recursive isomorphism of partial recursive functions (Q750426)

Let \(\alpha\) and \(\beta\) be partial recursive functions. \(\alpha\) is recursively isomorphic to \(\beta\) (\(\alpha\) resembles \(\beta\)) if there exists a recursive permutation f (there exist recursive permutations f and g) such that \(\alpha =f^{-1}\beta f\) \((\alpha =f^{-1}\beta g)\). The according equivalence classes are called isomorphism (resemblance) types. Isomorphism clearly implies resemblance, so resemblance types constitute several isomorphism types. What resemblance types are also isomorphism types? A final answer to this question has not been given. The only cases presently known are the type of the empty partial function, the type of all constant functions, and the type of all universal functions. In the paper under review the author proves some properties of functions whose resemblance types are also isomorphism types. For example, in Theorem 2 it is proved that if a partial recursive function \(\alpha\) is not empty and is not constant and if its resemblance type is also isomorphism type, then the range of \(\alpha\) is equal to \(\omega\) or is a simple set.