> On 21 Aug 2018, at 08:16, [email protected] wrote:
>
> I've been looking at the Wiki article on this topic. I find that I really
> don't understand what it is, or why it's important. Maybe a few succinct
> words from the usual suspects can be of help. TIA.
Actually, I have very recently wrote a long post on exactly this (Church’s
thesis), but I have decided to first explain the combinators …
Here I give you a simple explanation of what is Church’s thesis (also called
Post thesis, Kleene’s thesis, Turing’s thesis, or very often now; the Church’s
Turing thesis).
Do you know hat is a function? Do you know what is a function from N to N
(where N is the set of natural numbers, i.e. N = {0, 1, 2, 3, …}).
Now the set of all functions from N to N is very big, and big sets led often to
paradoxes, so people have tried to restrict the notion of function, and one of
the restriction has consisted in the “computable function”.
Intuitively, a computable function is a function (from N to N) for which we can
explain how to compute it (in a finite time, on its finite argument, and the
idea is that the explanation to compute the function have to be encodable in a
finite way).
For example, most functions studied by mathematicians are obviously computable,
and it is easy to convince oneself that a function is (intuitively) computable.
But people sought a precise definition of computable.
Church invented the “lambda calculus” formalism for that effect, like
independently Turing invented the Turing (digital) machine for that effect.
Church just defined a computable function by one that we can encode in his
lambda calculus. It is his student Kleene who understood that it is has to be
thesis (overlapping philosophy and mathematics). In fact Kleene will see that
the existence of universal formalism entails incompleteness quasi-directly.
Turing just defined a computable function by a function computable by a
machine, but he saw too that this was a philosophical thesis.
Turing showed, nevertheless the first equivalence theorem: a function is
computable by a Turing machine if and only if it is computable by a lambda
calculus expression (or a combinator).
Post did already,declared that a function is computable if and only if it is
computable in his formal definition (Post production system). Post too
understood that it was a postulate of high importance. Later it was proved that
a function is Post-calculable iff it is Turing calculable, iff it is Church
calculable, making all those thesis equivalent.
So the Church-Post-Kleene-Turing-markov … thesis is that a function (always
from N to N) is intuitively (human) computable if and only if it is computable
by any of those formal system.
Gödel will disbelieve in Church thesis, and miss it, despite proving that
arithmetic emulates all computable functions, but he was not sure he get them
all. Only after reading Turing, will Gödel accept the Church Turing thesis, and
thus definition of computable function.
Do you know Cantor theorem? Do you know the theorem asserting that the set of
functions from N to N (or from N to {0, 1}) is not enumerable?
If yes, I will show you that the Church Turing thesis entails incompleteness of
al all formal system rather easily. If no, I will send more explanation.
Have you tried to follow the thread of the combinators. This is again a formal
system capable of defining all computable functions. So, Church-thesis is
equivalent with “all intuitively computable functions are computable by
combinators”. I will prove this.
Tell me if this helped, I am not sure of your background.
Bruno
>
> --
> You received this message because you are subscribed to the Google Groups
> "Everything List" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected]
> <mailto:[email protected]>.
> To post to this group, send email to [email protected]
> <mailto:[email protected]>.
> Visit this group at https://groups.google.com/group/everything-list
> <https://groups.google.com/group/everything-list>.
> For more options, visit https://groups.google.com/d/optout
> <https://groups.google.com/d/optout>.
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
