Graduate studies at Western
|Abstract||We describe a proof by a computer program of the unsolvability of the halting problem. The halting problem is posed in a constructive, formal language. The computational paradigm formalized is Pure LISP, not Turing machines. The machine was led to the proof by the authors, who suggested certain function definitions and stated certain intermediate lemmas. The machine checked that every suggested definition was admissible and the machine proved the main theorem and every lemma. We believe this is the first instance of a machine checking that a given problem is not solvable by machine.|
|Keywords||No keywords specified (fix it)|
No categories specified
(categorize this paper)
|Through your library||Only published papers are available at libraries|
Similar books and articles
Sara Negri (2011). Proof Analysis: A Contribution to Hilbert's Last Problem. Cambridge University Press.
Herbert A. Simon & Stuart A. Eisenstadt (1998). Human and Machine Interpretation of Expressions in Formal Systems. Synthese 116 (3):439-461.
B. Jack Copeland (2002). Accelerating Turing Machines. Minds and Machines 12 (2):281-300.
Leonard M. Adleman & M. Blum (1991). Inductive Inference and Unsolvability. Journal of Symbolic Logic 56 (3):891-900.
Toby Ord & Tien D. Kieu (2005). The Diagonal Method and Hypercomputation. British Journal for the Philosophy of Science 56 (1):147-156.
Verónica Becher & Santiago Figueira (2005). Kolmogorov Complexity for Possibly Infinite Computations. Journal of Logic, Language and Information 14 (2):133-148.
B. Jack Copeland & Oron Shagrir (2011). Do Accelerating Turing Machines Compute the Uncomputable? Minds and Machines 21 (2):221-239.
Gabor T. Herman (1969). The Unsolvability of the Uniform Halting Problem for Two State Turing Machines. Journal of Symbolic Logic 34 (2):161-165.
Paolo Cotogno (2009). A Brief Critique of Pure Hypercomputation. Minds and Machines 19 (3):391-405.
Added to index2009-01-28
Total downloads8 ( #131,868 of 739,375 )
Recent downloads (6 months)1 ( #61,680 of 739,375 )
How can I increase my downloads?