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

[Richard Heck]

On 08/22/2016 04:58 PM, Yiannis N. Moschovakis wrote:
> 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....

Turing writes in the 1936 paper, at the beginning of section 9:

No attempt has yet been made to show that the "computable" numbers
include all numbers which would naturally be regarded as computable. All
arguments which can be given are bound to be, fundamentally, appeals
to intuition, and for this reason rather unsatisfactory mathematically.
The real question at issue is "What are the possible processes which can be
carried out in computing a number?"

Turing goes on to give his famous arguments for the Church-Turing thesis,
one of which consists largely of a philosophical analysis of the notion of
a "possible process[] which can be carried out in computing a number".
Surely this question is naturally interpreted as: What are algorithms?

Richard Heck

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160822/89a3460f/attachment-0001.html>