Is the Halting problem effectively solvable non-algorithmically, and is the Goedel sentence in NP, but not in P?
| dc.creator | Anand, Bhupinder Singh | |
| dc.date | 2005-06-07 | |
| dc.date.accessioned | 2026-07-07T05:20:35Z | |
| dc.date.available | 2026-07-07T05:20:35Z | |
| dc.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. | |
| dc.description | 12 pages; an HTML version is available at http://alixcomsi.com/Is_the_Halting_problem.htm | |
| dc.identifier | https://arxiv.org/abs/math/0506126 | |
| dc.identifier | http://arxiv.org/abs/math/0506126 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/75429 | |
| dc.subject | General Mathematics | |
| dc.subject | 03B10 | |
| dc.title | Is the Halting problem effectively solvable non-algorithmically, and is the Goedel sentence in NP, but not in P? | |
| dc.type | text |