Is the Halting problem effectively solvable non-algorithmically, and is the Goedel sentence in NP, but not in P?
Abstract
Description
We consider the thesis that an arithmetical relation, which holds for any, given, assignment of natural numbers to its free variables, is Turing-decidable if, and only if, it is the standard representation of a PA-provable formula. We show that, classically, such a thesis is, both, unverifiable and irrefutable, and, that it implies the Turing Thesis is false; that Goedel's arithmetical predicate R(x), treated as a Boolean function, is in the complexity class NP, but not in P; and that the Halting problem is effectively solvable, albeit not algorithmically.
12 pages; an HTML version is available at http://alixcomsi.com/Is_the_Halting_problem.htm
12 pages; an HTML version is available at http://alixcomsi.com/Is_the_Halting_problem.htm