[FOM] "algorithm" and the Church-Turing Thesis

[Yiannis N. Moschovakis]

Martin is absolutely right in saying that "the Church-Turing
Thesis says nothing about what algorithms ARE. It is about what
algorithms can and can not DO", a not-so-subtle point which is
often misunderstood.

However, the historical point he makes is not entirely correct: it
is true that Turing, Kleene and (as far as I know) Post never
mentioned algorithms in their fundamental papers on the
Church-Turing Thesis, but Church did, in his 1936 paper "An
unsolvable problem in elementary number theory", in the American
Journal of Mathematics. In Section 7 of this paper, he says

    "Conversely it is true, under the same definition of
     effective calculability, that every function, an algorithm
     for the calculation of the values of which exists,
     is effectively calculable. For example, in the case of
     a function F of one positive integer, an algorithm consists ..."

and follows that with a tentative "definition" that applies most
directly to Goedel's reckonability and for which he sounds almost
defensive. His Footnote 19: "If this representation or some
similar one is not allowed, it is difficult to see how the notion
of an algorithm can be given any exact meaning at all".

Yiannis


On Mon, Aug 22, 2016 at 11:57 AM, Martin Davis <martin at eipye.com> wrote:

> The ongoing discussion on "Counterfactuals in relative computability
> theory" seems to take as a given that the Church-Turing Thesis makes
> precise the notion of "algorithm". But the Church-Turing Thesis says
> nothing about what algorithms ARE. It is about what algorithms can and can
> not DO. So for a given set S of natural numbers, the Church-Turing Thesis
> asserts that there is an algorithmic method for determining of a given
> natural number whether or not it belongs to S if and only if S is Turing
> computable.
>
> BTW the word "algorithm" occurs in none of the key founding papers by
> Church, Turing, Post, Kleene.
>
> Martin
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160822/d0127c62/attachment.html>