Recursion Theorems and Effective Domains

ID
TR-84-22
Authors
Akira Kanda
Publishing date
January 1984
Abstract
Every acceptable numbering of an effective domain is complete. Hence every effective domain admits the 2nd recursion theorem of Eršov [1]. On the other hand for every effective domain, the 1st recursion theorem holds. In this note, we establish that for effective domains, the 2nd recursion theorem is strictly more general than the 1st recursion theorem, a generalization of an important result in recursive function theory.