Inductive inference and unsolvability
Leonard M. Adleman, Manuel Blum · Journal of Symbolic Logic · 1991
Abtract It is shown that many different problems have the same degree of unsolvability. Among these problems are: The Inductive Inference Problem. Infer in the limit an index for a recursive function f presented as f(0), f(1),f(2),…. The Recursive Index Problem. Decide in the limit if i is the index of a total recursive function. The Zero Nonvariant Problem. Decide in the limit if a recursive function f presented as f(0), f(1), f(2),… has value unequal to zero for infinitely many arguments. Finally, it is shown that these unsolvable problems are strictly easier than the halting problem.