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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~----------~----~----~----~------~----~------~--~---