the Halting Problem
I wanted to write a nice, simple, clear, modern presentation of the incomputability of halting that programmers would appreciate.
But I soon discovered that it was not so simple and clear as I had hoped.
In my earliest paper on this topic, it seemed to me that an argument could be made that the "halting function" has an inconsistent
specification, so no function is specified, so no function is proved incomputable.
In more recent papers, my argument is that the inconsistency arises only when you ask for a program in some language to compute halting for all programs in that same language.
But if you want to compute halting for all programs in one language, you might do so by writing your program in another language.
Of course, I'm perfectly aware that this contradicts the universally accepted position that halting has been proven to be incomputable.
If you can show me where my arguments go wrong, I would be grateful. Do not just quote authority; that's useless and unscientific.
On the other hand, if you agree with my arguments, I would also like to know that.
If you are interested, start at the top of the list and work down.
In order to make each paper self-contained, there is some overlap. Maybe the top 3 papers (17 pages in total) say enough.
Read them critically, and form your own opinion.
Then contact me at firstname.lastname@example.org.
- Epimenides, Gödel, Turing: an Eternal Gölden Tangle, 6 pages, 2014 August 29
- Objective and Subjective Specifications, 6 pages, 2017 July 10, WST Workshop on Termination, Oxford, 2018 July 18
- Observations on the Halting Problem, 5 pages, 2014 December 23
- How to Compute Halting, 5 pages, 2014 January 2
- a Tale of Two Turing Machines, 2 pages, 2016 October 20
- Programs, Specifications, and Halting, 5 pages, 2014 November 17
- Halting Problem, 3 pages, 2014 January 29
- Reconstructing the Halting Problem, 5 pages, 2013 April 23
- Problems with the Halting Problem, COMPUTING2011 Symposium on 75 years
of Turing Machine and Lambda-Calculus, Karlsruhe Germany, invited, 2011 October 20-21;
Advances in Computer Science and Engineering v.10 n.1 p.31-60, 2013
- the Computability Hierarchy,
Advances in Computer Science and Engineering, v.10 n.2 p.123-131, 2013
- the Halting Collection, 10 pages, 2015 January 4
- Diagonalize Then Reduce, 2 pages, 2016 November 8
- Incomputability According to aPToP, 4 pages, 2015 August 13
- History of my Problems with the Halting Problem 2013 August 14 and 2014 July 6
- the Jeffrey Shallit Affair 2014 January 14