On Thursday, August 23, 2018 at 7:02:21 PM UTC, Bruno Marchal wrote:
>
> Grayson,
>
> Let me explain you something crazy but absolutely important to understand
> about the set of all computable function from N to N.
>
> It is true that later, we will be able to identify that with the
> computable real numbers, but that is another story.
>
> So what is a computable function from N to N?
>
> It is a function from N to N, i.e. an association to each natural numbers
> to some other or not natural number.
>
*If you include "or not a natural number", you have a range R (or possibly
domain), the real numbers, which is not what you assert as the definition
of the function at hand. Incidentally, I am traveling by car for a few
days, so it will take some time to study your latest posts. I plan to study
Cantor's theorem on the Internet and compare it with you proof. AG*
>
> The notion admits generalisation, like the function from N x N to N, that
> is, the function with many variables.
>
> But what means computable?
>
> It means you can explain, in a finite time, how to compute its values and
> this in a finite time for each value.
>
> You can explain to who?
>
> To the dumbest people in the room. OK, we will come back on this one, but
> at first the notion of computable seems to be epistemological, and depends
> on the ability of the subject. How could we dream to define mathematically
> that notion.
>
> Gödel already used a version of Cantor Diagonal to show that all theories
> (rich enough to axiomatise elementary arithmetic) are essentially
> undecidable, and that there were no universal provability predicate. And
> Traski, but also Gödel proves a similar result for the undefinability of
> truth.
>
> So how to hope for this? If only a Miracle!
>
> Let me show you the miracle. Probably not in one post. First I will show
> you that the class or set or collection of the computable functions is NOT
> computable, and in fact it does not admit a universal computable function!
> No universal machine in that class and for this class!
>
> Take a rest, and then we start. If you understand this, you will
> understand something which I think is truly amazing.
>
> I need somme lemma.
>
> Take an alphabet, A = {a, b}. You can build words with the element of the
> alphabet, like a, b aa, ab, … aabbabbaabbb, etc. Let A* be the set of all
> finite words on A.
>
> As long as the alphabet is finite, the set of words will be enumerable.
> OK? I mean there is a bijection (a one-one and onto function) from the set
> of words and N. To see it, it is enough to order them lexicographically:
> that is by length, and alphabetically for those who have the same length.
>
> That gives for {a, b}, with 0 on the empty word.
>
> 1- a
> 2) b
> 3) aa
> 4) ab
> 5) ba
> 6) bb
> 7) aaa
> 8) aab
> ...
>
> So we can enumerate the finite words. BTW, this shows immediately that the
> rational numbers are enumerable, just enumerate their description in
> English, like#one#on#two, or thirty#five#on#twenty#four, …
>
> Usually the diagonal is used to show that something is impossible. Take
> A** the set of infinite words!
>
> It can be shown easily (but I will pass) that there is a bijection between
> A** and the real number, and the set of subset of N, and the set of
> functions of N to N (or to any finite non empty set).
>
> Let me just show, or remind, you how the Cantor diagonal shows that there
> is no bijection between N and A**, with A = {0, 1}.
>
> If there was a bijection between N and the set of all infinite sequence,
> you would have a matrix like
>
> 0 ----------------- 0100111010..
> 1 ----------------- 11011111100…
> .2 ----------------- 10000011011...
> …
>
> That is, for all i
>
> i ----------------- a_i1 a_i2 a_i3 …
>
> But once that bijection is supposed to exist, it is easy to find a
> sequence of one and zero which is not in the sequence: it is the diagonal
> sequence:
>
> (flip_00)(flip_11)(flip_22)(flip a_33)(flip a_44)(flip a_55) ...
>
> It is the diagonal in the correspondence above, but where each 0 have flip
> to 1, and each 1 have flip to zero (by subtracting them from 1).
>
> That sequence cannot be in the list above, because if that was the case it
> would correspond to number k,
> And (a_kk) would be equal to flip (a_kk). CQFD. OK?
>
> Do you see that, Grayson?
>
> I have to go. Sorry. It is easier on on board with the chalk.But you have
> to understand the passage above, so tell me if it is OK.
>
> I guess some have an idea of the miracle I am talking about, but perhaps
> they don’t realise the true nature of the creative bomb here. The term
> “miracle” comes from Gödel, and refer to the fact that despite the set of
> computable functions from N to N is not computable, the set of all
> computable functions from subset (including N!) of N to N, will be
> computable, but then at the price of non controllability,
>
> Later II will show some direct link between the phi_i and the combinators,
> and explore a bit the frontier between the computable and the non
> computable. The Löbian combinators are those who, in some precise technical
> sense, understand or discover all this. It is the dumbest stupid in the
> room, when he get deluded by the induction axioms … soon it hallucinates
> worlds beyond words ...
>
> 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].
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.
