> On 22 Aug 2018, at 22:59, [email protected] wrote:
>
>
>
> 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,
OK, when possible of course.
> but never one-to many. AG
Yes. For example temperature at a place is a function of time; because at no
time we get two temperature at the same place. That is what is important with
function, they give only one output.
>
> 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
Amazingly, polynomial roots finding is computable on the real numbers, but not
computable on the natural numbers. So yes, they are many subtleties there. We
will plausibly meet one soon or later.
>
> 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
You need symbols q1, q2, q3, … called configuration symbols,
You need some alphabet symbols S0, S1, S2, ... called tape symbols,
And you need two special symbols R and L read Right and Left.
Then a quadruple is defined by any expression having the shape
qi Sj Sk ql
or
qi Sj R ql
or
qi Sj L ql
A Turing machine is defined as a finite set of quadruples.
The machine is thought as reading some linear tape, with perhaps some tape
symbols written on it, and the working of the machine is determined by its
current state, the current symbols it looks, and what its quadruple determined
from that:
qi Sj Sk ql means that if I am in state qi, in front of the symbol tape Sj,
then I (over)write Sk there, and I am in state ql now.
qi Sj R ql means that if I am in state qi in front of the symbol state Sj,
then I move one step on the right, and get the state ql now.
qi Sj L ql means that if I am in state qi in front of the symbol state Sj,
then I move one step on the left, and get the state ql now.
Exemple: Where S0 = “0", and S1 = “1”, the machine {q1 1 0 q1, q1 0 R q1} will
erase all “1” appearing on its tape on her right: that computation (which never
stop) is described by the sequence, assuming the tape contains 0010110… I use
the state of the machine to indicate where she reading the tape, and in which
state
(q1)0010110
0(q1)010110
00(q1)10110
00(q1)00110. ; the machine has erased a 1
000(q1)0110
0000(q1)110
0000(q1)010 ; again
00000(q1)10
00000(q1)00 ; again
000000(q1)0
0000000(q1)
…
Note that Turing did use quintuples, and allow its machine to both erase and
move (L or R) simultaneously. There are many other variants, but they all
compute the same class of functions from N to N.
If there are no two quadruples beginning with the same qi Sj, the machine is
said deterministic. If not, the machine is said non deterministic.
You can enumerate all Turing machine TM1, TM2, TM3, TM4, … (OK?-
A universal Turing machine is a Turing machine (i.e. finite set quadruplets)
such that if two numbers are put on its tape, like 12 and 2 below (numbers are
coded here by 0, 1, 2, …. = 1, 11, 111, …)
1111111111111011100000000000000000000000000000…
then it will mimic exactly the 12th Turing machine TM12 on the argument 111.
That has been discovered by Post and Kleene independently (ye, Post discovered
the Turing machine too).
>
> 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
I will elaborate on this later, but it just means that Turing and Post have
given very different notion of computability, but then prove their equivalence.
>
> 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
A function is computable means, intuitively, that we can explain (in a finite
time) how to compute it (in a finite time for each argument).
Unlike provability and definability, which depends on the choice of the
theory/formalism, computability is the same whatever formalism is used. A
modern day physical computer is a physical implementation of such formalism,
and they too compute always the same class of functions. More on this later.
>
> 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
Gödel find hard to believe that we obtained a absolute definition of
computability. He was the guy showing that this does not exist for provability,
nor definability. But he will be convinced by his reading of Turing. Despite he
made the big part of the job, he missed the Church-Turing thesis. He could have
claimed the contrary, because he get very close to it in a footnote of one of
his paper, but very honestly declined this honour and admit to have missed it.
He considered it as a sort of miracle, and he is right on this. The closure of
computable function for Cantor-like diagonal is indeed the most extraordinary
fact I have ever lived in my life. I will try to share why later. It took me
also much time before I accept it.
>
> 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.
Not really. I was referring to cantor’s diagonal proof that the irrationals are
NOT countable.
> I can believe the latter comment, and can see it's not easy to prove. AG
The countability of the rationals is easy. The non countability of the reals is
less easy, but still rather easy.
I will come back on this.
>
> 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
I suggest you do. It is a very fundamental theory, at the base of all
programming languages, practically and theoretically. It is also very simple
(once we get the notation right).
>
> 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
I suggest you read the combinators thread, or wait for my post on Church thesis.
If you want, you can play the role of the candid guy, in which case I send much
shorter post, and you answer by saying "OK, I get it", or by “Don’t get it”,
and I try another explanation.
Computability theory is far more easy than quantum mechanics, and eventually as
much astonishing (and with mechanism, it becomes ultra-fundamental …).
I have to go now. I intent to send the combinator II sequel, still today, it is
still time to take the wagon …
It is easier than Church-thesis, which people sometimes believe it is obvious,
or just a definition, when it is not (but that is not so obvious!). In fact,
Church missed it too apparently. It is Kleene and Post who will grasp the best
its miraculous totally unbelievable nature, and its consequences.
Bruno
>
> 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
>> <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]
> <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.
