Hi Quentin,
Le 07-juin-06, à 15:56, Quentin Anciaux a écrit :
>
> Hi Bruno,
>
> what I undestand about the UD is that it generates all programs, a
> program
> being simply a number from the set N.(1)
This is right. Programs or digital machine are supposed to be
(grammatically) well-defined, and this means that we can check in
finite time if some string is a well defined program for some universal
machine. Program like digital machines, or like ourself with comp, are
also supposed to be finite or finitely describable. From that, having
fixed a particular universal machine, we get a computable bijection
between N and the set of all programs. A choice of a Universal Machine
is akin to a choice of a base in a vector space. In each case the
choice makes it possible to ascribe numbers to the mathematical
entities under considerations (natural number for program/machine),
real or complex number for vectors.
In geometry, interesting theorems does not depend of the choice of the
base. In computer science, it is the same. Interesting theorem should
not depend on the choice of the particular universal machine. Of
course I will have to say more on this.
>
> There exists an infinity of program which generates a set of growing
> function
> (different set), all the computable growing function are generated by
> all
> these programs(taken as a whole). Is this correct ?
Taken as a whole: yes.
Alas that whole set cannot be generated mechanically (algorithmically,
by a computer/universal machine). If it was, then the diagonalization
would prove 0=1 again!
That is why, when given a name for a *big* finite number, like
[omega[omega]omega] applied to (9 [9] 9) I have only use a "tiny" part
of the nameable (constructive) ordinal.
Now, if you accept some set theory, obviously you can consider the set
of all constructive ordinals. That gives the first non constructive
ordinal. His name is omega1^CK. CK is for Church and Kleene who found
it. It cannot be constructive, and cannot be generated by a program,
but you can generated bigger and biiger part of it. Note that omega1^CK
is still enumerable (countable, in bijection with N).
Mysterious? Not at all: you will see (I prefer to keep the solution in
one post; so: see later).
With the growing functions from N to N, either you have a set of
names/codes/descriptions/programs which you can generate, but then it
is incomplete, it miss some growing functions; or your set of growing
functions is complete, but then you cannot generate it. We will see
many other examples of sets having similar property.
> Is this metaset also
> diagonalisable ?
It depends of what you mean by a set being diagonalizable? If it is
really the whole set, then, you can get only by building a special
progression on the whole of omega1^CK, and this cannot be done
mechanically. So the whole set will be vaccinated against programmable
diagonlization.
At some point we will have to distinguish carefully among effective
(programmable) diagonalization and some non-constructive (non
programmable) one.
> I said no, because if it was then there is a contradiction
> with the premises that said that we generate *all* the programs that
> compute
> growing functions, thus either we cannot generate those programs (but
> that
> would be strange, that would means N is not enumerable ?) or the
> "metaset" is
> not diagonalisable...
>
> Where do I fail in my understanding ?
I will try to be clear on this asap (still today). Of course N is
enumerable!
>
> Thanks,
> Quentin
>
> (1) I still have another problem with that because a program to be run
> need
> also the coding scheme (the instruction set of the turing machine that
> run
> it), which instruction set the UD use ? or how it construct it ?
A particular UD will just use the(finite number of) instructions of
some particular Universal machine.
Do you recall the SK-combinator programming language? It has an
incredibly simple syntax given that "S" is a program, "K" is a program,
and then all the other programs have been defined "recursively" or "by
induction" from that: if x et a program and y is a program, then (x y)
is a program.
So K, S, (K K), (K S) (S K) (S S) ((K K) K) ((K S) K) ... are all
programs.
In that case, a UD will be programmed by a finite string of S and K +
parentheses.
A UD written in Fortran (resp. lisp) will be a a fortran program. Of
course you can write in Fortran a UD which dovetails on the LISP
programs, and reciprocally ... More will be said, but if, after that,
there are still unclear points don't hesitate to ask ('course).
Bruno
http://iridia.ulb.ac.be/~marchal/
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Everything List" group.
To post to this group, send email to everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list
-~----------~----~----~----~------~----~------~--~---
Received on Thu Jun 08 2006 - 09:15:49 PDT