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 hehner@cs.utoronto.ca. author's website