On 05 Jun 2009, at 14:23, ronaldheld wrote:
> 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)
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 email@example.com
To unsubscribe from this group, send email to
For more options, visit this group at