Church's thesis

Church's thesis

[¦chərch·əz ¦thē·səs]
(mathematics)
The claim that a function is computable in the intuitive sense if and only if it is computable by a Turing machine. Also known as Turing's thesis.
References in periodicals archive ?
The purpose of this article is to sharpen Priest's argument, avoiding reference to informal notions, consensus, or Church's thesis. We add Priest's dialetheic semantics to ordinary Peano arithmetic PA, to produce a recursively axiomatized formal system P[A.sup.[starf]] that contains its own truth predicate.
(So that readers really get their money's worth, I also refute Church's Thesis.) Early versions of some of these arguments can be found on my web site.
Furthermore, if we conceive of Church's Thesis as asserting that a function is 'intuitively' computable if and only if it is a partial recursive function (and this is surely a common conception of Church's Thesis), then the presupposition in Young [1977] amounts to no more than the application of the if direction of Church's Thesis to the resource bounded computations of complexity theory.
we need an inductive machine which can formalize its own metalanguage if that machine is to produce its own godel-formula; but such a formalization would be seemingly non-algorithmic, and hence, the suggestion implicit seems to be that it would be computationally impossible (assuming Church's Thesis) ...
If the first interpretation is intended, it implies that Church's thesis stands in need of extension to incorporate explicitly the notion of 'function computable by a parallel machine'.