A mechanical proof of the unsolvability of the halting problem

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)
Categories (categorize this paper)
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history
Request removal from index
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 26,162
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles
A Brief Critique of Pure Hypercomputation.Paolo Cotogno - 2009 - Minds and Machines 19 (3):391-405.
Kolmogorov Complexity for Possibly Infinite Computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
The Diagonal Method and Hypercomputation.Toby Ord & Tien D. Kieu - 2005 - British Journal for the Philosophy of Science 56 (1):147-156.
Inductive Inference and Unsolvability.Leonard M. Adleman & M. Blum - 1991 - Journal of Symbolic Logic 56 (3):891-900.
Accelerating Turing Machines.B. Jack Copeland - 2002 - Minds and Machines 12 (2):281-300.

Monthly downloads

Added to index

2009-01-28

Total downloads

27 ( #185,115 of 2,152,538 )

Recent downloads (6 months)

1 ( #399,788 of 2,152,538 )

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Order:
There  are no threads in this forum
Nothing in this forum yet.

Other forums