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-l...@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---