On 05 Jun 2009, at 14:23, ronaldheld wrote:

> Bruno:
> I understand a little better. is there a citition for a version of
> Church Thesis that all algorithm can be written in

The original Church Thesis, (also due to Post, Turing, Markov, Kleene,  
and others independently)

is this:

A function is computable if and only if it is programmable in LAMDA  

Then it is an easy but tedious exercise of programing to show that you  
can simulate LAMDA CALCULUS with FORTRAN, and that you can simulate  
FORTRAN with LAMBDA CALCULUS. So they compute the same functions.

And the same is true with LISP, or JAVA, or ALGOL, or C++, etc... in  
the place of FORTRAN.

A thorough introduction to Church thesis, and I would say one far  
deeper than usual, is integrally part of the seventh step of UDA. So  
we will come back on this soon or later. Church thesis is really the  
key and the motor of both UDA and AUDA. I have discovered that it is  
rarely well understood, even by many "experts". Like Gödel's theorem,  
Church's thesis is often deformed or misused.



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@googlegroups.com
To unsubscribe from this group, send email to 
For more options, visit this group at 

Reply via email to