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.
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.
