Is the Halting problem effectively solvable non-algorithmically, and is the Goedel sentence in NP, but not in P?

Details Is the Halting problem effectively solvable non-algorithmically, and is the Goedel sentence in NP, but not in P? Is the Halting problem effectively solvable non-algorithmically, and is the Goedel sentence in NP, but not in P?

2005-06-07

arxiv.org/abs/math/0506126v1

Mathematics

General Mathematics

12 pages; an HTML version is available at http://alixcomsi.com/Is_the_Halting_problem.htm

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Is the Halting problem effectively solvable non-algorithmically, and is the Goedel sentence in NP, but not in P? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Is the Halting problem effectively solvable non-algorithmically, and is the Goedel sentence in NP, but not in P?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Is the Halting problem effectively solvable non-algorithmically, and is the Goedel sentence in NP, but not in P? will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-538648