A case for weakening the Church-Turing Thesis

Details A case for weakening the Church-Turing Thesis A case for weakening the Church-Turing Thesis

2011-08-20

arxiv.org/abs/1108.4597v1

Mathematics

General Mathematics

22pages. an updated version of this manuscript is accessible at http://alixcomsi.com/30_Church_Turing_Thesis_Update.pdf . arXi

Scientific paper

We conclude from Goedel's Theorem VII of his seminal 1931 paper that every recursive function f(x_{1}, x_{2}) is representable in the first-order Peano Arithmetic PA by a formula [F(x_{1}, x_{2}, x_{3})] which is algorithmically verifiable, but not algorithmically computable, if we assume that the negation of a universally quantified formula of the first-order predicate calculus is always indicative of the existence of a counter-example under the standard interpretation of PA. We conclude that the standard postulation of the Church-Turing Thesis does not hold if we define a number-theoretic formula as effectively computable if, and only if, it is algorithmically verifiable; and needs to be replaced by a weaker postulation of the Thesis as an equivalence.

Affiliated with

Also associated with

No associations

Rating

A case for weakening the Church-Turing Thesis 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 A case for weakening the Church-Turing Thesis, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A case for weakening the Church-Turing Thesis will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-244569