Le 15-janv.-09, à 20:55, Brent Meeker a écrit :

>> Stathis is not wrong but seems unclear on what a computation
>> mathematically is perhaps.
>> Many miss Church thesis. The fact that there is a purely mathematical
>> notion of computation at all.
> I thought the Church's thesis was that all effectively computable 
> functions were
> in the lambda-calculus, but the "effectively" referred to intuitive 
> ideas of
> what is physically realizable.

In the foundation of mathematics, including theoretical computer 
science, the word "effectivity" refers to either to Turing or Church or 
equivalent notion of mathematical computability, or just, with Church 
Thesis, to computability.
For intuitionist it can refer to even more abstract (unphysical) 
notions of constructivity

> Later it was shown that the recursive functions
> and the Turing functions also defined the same set of effectively 
> computable
> functions.

Yes. All formalism which has been invented to describe the computable 
functions by finite vmeans have led to the same class of functions. It 
is the "empirical" argument for the thesis by Church, Post, Turing. 
Emil Post is the first to give a name to that thesis.

> Turing was plainly motivated by considering physically implemented
> computations.

Give me a reference. Turing did have a large spectrum of interest, 
including biology, chemistry and quantum physics. For example, the 
quantum Zeno effect has been discovered by Turing, but he did not 
publish it. But in his seminal 1936 paper on computability (which can 
be found in Davis 1964 book, reedited by Dover one year ago), there is 
no references to physics at all. On the contrary, the definition is 
inspired directly by what a human mathematician can compute using paper 
and a pencil, with refrence only to his mental state.

I must go. I will probably comment your other post tomorrow, because 
I'm rather busy today.



You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to everything-l...@googlegroups.com
To unsubscribe from this group, send email to 
For more options, visit this group at 

Reply via email to