On Tuesday, August 21, 2018 at 9:59:30 AM UTC, Bruno Marchal wrote:
>
>
> On 21 Aug 2018, at 08:16, [email protected] <javascript:> 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, …}).
>
*Yes, They're correspondences between two sets; many-to-one, one-to-one,
but never one-to many. AG *
>
> 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).
>
*Any subtle problems computing a simple polynomial or trigonometric
function? AG*
>
> 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).
>
> *What is a Turing machine? AG*
> 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.
>
*Please elaborate. AG*
>
> 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.
>
*Please elaborate. AG *
>
> 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.
>
*Please elaborate. AG*
>
> 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?
>
.
*Are you referring to Cantor's diagonal proof that the rationals are
countable? I've seen that. I can believe the latter comment, and can see
it's not easy to prove. AG *
>
> 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.
>
*No. AG*
> 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.
>
*Still pretty vague. I have a BA & MA in mathematics, and an MS in physics,
respectively from Cornell University, The University of Michigan, and
Northeastern University, AG *
>
> 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] <javascript:>.
> To post to this group, send email to [email protected]
> <javascript:>.
> Visit this group at https://groups.google.com/group/everything-list.
> For more options, visit 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.
