Eric Hehner: Problems with the Halting Problem

Thursday, Sept. 25, 2014, 3-4 p.m.
EN-4002

Either we leave the definition of the halting function incomplete, not saying its result when applied to its own program, or we suffer inconsistency. If we choose incompleteness, we cannot require a halting program to apply to programs that invoke the halting program, and we cannot conclude that it is incomputable. If we choose inconsistency, then it makes no sense to propose a halting program. Either way, the incomputability argument is lost. This invited talk was presented at COMPUTING 2011 Symposium on 75 years of Turing Machine and Lambda-Calculus, Karlsruhe Germany, 2011 October 20-21. It was presented at the 50th anniversary of IFIP WG2.1 in Rome on 2012 February 7. It has been published in Advances in Computer Science and Engineering, 2013 March. http://www.cs.utoronto.ca/~hehner/PHP.pdf

See http://www.engr.mun.ca/~theo/Misc/RicsTalks.html


Contact

Marketing & Communications

230 Elizabeth Ave, St. John's, NL, CANADA, A1B 3X9

Postal Address: P.O. Box 4200, St. John's, NL, CANADA, A1C 5S7

Tel: (709) 864-8000