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.
In order to make each paper self-contained, there is some overlap.
Read them critically, and form your own opinion.
Then contact me at email@example.com.
Here is a video made from some of the papers.
- Epimenides, Gödel, Turing: an Eternal Gölden Twist, 6 pages, 2014 August 29
- Objective and Subjective Specifications, 6 pages, 2017 July 10, WST Workshop on Termination, Oxford, 2018 July 18
- Halting, the Power of Mathematics, and Religion, 7 pages, 2020 September 20
- Epimenides, Gödel, Turing: an Eternal Gölden Twist, 19 pages, SN Computer Science v.1 p.308, 2020 September. This paper includes the first three papers in this list.
- Observations on the Halting Problem, 5 pages, 2014 December 23
- the Halting Program, 3 pages, 2020 August 5
- 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
- Halting According to aPToP, 7 pages, 2019 January 14
- History of my Problems with the Halting Problem 2013 August 14 and 2014 July 6
- the Jeffrey Shallit Affair 2014 January 14