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.
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list+unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Fri Jan 16 2009 - 06:18:44 PST