Effectivity questions for Kleene's recursion theorem

The present paper investigates the quality of numberings measured in three different ways: (a) the complexity of finding witnesses of Kleene's Recursion Theorem in the numbering; (b) for which learning notions from inductive inference the numbering is an optimal hypothesis space; (c) the complexity needed to translate the indices of other numberings to those of the given one. In all three cases, one assumes that the corresponding witnesses or correct hypotheses are found in the limit and one measures the complexity with respect to the best criterion of convergence which can be achieved. The convergence criteria considered are those of finite, explanatory, vacillatory and behaviourally correct convergence. The main finding is that the complexity of finding witnesses for Kleene's Recursion Theorem and the optimality for learning are independent of each other. Furthermore, if the numbering is optimal for explanatory learning and also allows to solve Kleene's Recursion Theorem with respect to explanatory convergence, then it also allows to translate indices of other numberings with respect to explanatory convergence.

Authors

• John Case
• Sanjay Jain
• Frank Stephan

Keywords

• Inductive inference
• Kleene's Recursion Theorem
• Kolmogorov complexity
• Optimal numberings