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

Tue Aug 23 17:34:53 EDT 2016

  Maybe you know this matter, but for any case, I would like to inform
about two books devoted to Church's Thesis. The first one is: Adam
Olszewski, Jan Wolenski and Robert Janusz (Eds.), "Church's Thesis After
70 Years", Ontos Verlag 2006. There are included, among others, the
chapters: Andreas Blass and Yuri Gurevich, "Algorithms: a Quest for
Absolute Definitions" and B. Jack Copeland, "Turing's Thesis". 

  One of the Editors of this book, Adam Olszewski, is also the Author of
the book: "Church's Thesis. The Historico-Philosophical Context",
UNIVERSITAS, Krakow 2009 (originally published in Polish, maybe an
English edition of this book, also exists - I don't know). 

                                    Lukasz T. Stepien

---

Lukasz T. Stepien

The Pedagogical University of Cracow
The Institute of Computer Science,
ul. Podchorazych 2
30-084 Krakow
Poland

tel. +48 12 662-78-54, +48 12 662-78-44

The URL  http://www.ltstepien.up.krakow.pl

On 2016-08-22 20:57, Martin Davis 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/20160823/be67fd69/attachment.html>