Getting around the Halting Problem

X. Y. Newberry

The Halting Theorem establishes that there is no program (or Turing machine) H that can decide in all cases if an arbitrary program n halts on input m. The conjecture of this paper is that nevertheless there exists a sound program H such that if it halts it answers either yes or no, and can also in a certain sense identify all the cases it is unable to decide. The Halting Theorem can be proved by constructing a "counterexample', i.e. a program that attempts to assert that it itself does not halt. The thesis is that there exists a program that proves about itself that its own attempt to prove, that the counterexample does not halt, does not halt. This outcome can be interpreted as 'it is NOT TRUE that the counterexample does not halt' as opposed to 'it is FALSE that the counterexample does not halt.' This becomes possible when a non-bivalent logic is used, and the Recursion Theorem is reinterpreted as mutual necessitation rather than equivalence.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment