Inductive inference and unsolvability
Journal of Symbolic Logic 56 (3):891-900 (1991)
| Abstract | 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 | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,679 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesJoseph R. Shoenfield (1972). Degrees of Unsolvability. New York, American Elsevier.
Martin Davis (ed.) (1965/2004). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems, and Computable Functions. Dover Publication.
Bernhard Lauth (1993). Inductive Inference in the Limit for First-Order Sentences. Studia Logica 52 (4):491 - 517.
Emil L. Post (1947). Recursive Unsolvability of a Problem of Thue. Journal of Symbolic Logic 12 (1):1-11.
Mark Changizi (1996). Function Identification From Noisy Data with Recursive Error Bounds. Erkenntnis 45 (1):91 - 102.
John D. Norton (2003). A Material Theory of Induction. Philosophy of Science 70 (4):647-670.
Stephen Hetherington (2001). Why There Need Not Be Any Grue Problem About Inductive Inference as Such. Philosophy 76 (1):127-136.
Dwight R. Bean (1976). Effective Coloration. Journal of Symbolic Logic 41 (2):469-480.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads3 ( #201,930 of 549,070 )Recent downloads (6 months)1 ( #63,317 of 549,070 )How can I increase my downloads? |
My notes
Discussion
