Inductive Inference and Unsolvability
Adleman, Leonard M. ; Blum, M.
J. Symbolic Logic, Tome 56 (1991) no. 1, p. 891-900 / Harvested from Project Euclid
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),\ldots$. 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),\ldots$ has value unequal to zero for infinitely many arguments. Finally, it is shown that these unsolvable problems are strictly easier than the halting problem.
Publié le : 1991-09-15
Classification: 
@article{1183743737,
     author = {Adleman, Leonard M. and Blum, M.},
     title = {Inductive Inference and Unsolvability},
     journal = {J. Symbolic Logic},
     volume = {56},
     number = {1},
     year = {1991},
     pages = { 891-900},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183743737}
}
Adleman, Leonard M.; Blum, M. Inductive Inference and Unsolvability. J. Symbolic Logic, Tome 56 (1991) no. 1, pp.  891-900. http://gdmltest.u-ga.fr/item/1183743737/