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

[Yiannis N. Moschovakis]

Prompted by Vardi's post, I thought I might point to the slides
from my remarks in the panel discussion which motivated his
article and the paper (mostly on the Church-Turing Thesis) that
I wrote after the meeting: they are posted at
http://www.math.ucla.edu/~ynm/lectures/2011dlmps.pdf and
http://www.math.ucla.edu/~ynm/papers/ynm2014.pdf

I think that the problem of "defining" algorithms is important for
the foundations of the theory of computation and has not received
the attention it deserves. The paper cited above gives
(incomplete) references to some of the work that has been done on
it, mostly by Yuri Gurevich (and his collaborators) and myself.

Yiannis


On Mon, Aug 22, 2016 at 4:00 PM, Richard Heck <richard_heck at brown.edu>
wrote:

> 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
>
>
> _______________________________________________
> 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/20160823/203023fe/attachment.html>