Le 08-juin-06, à 02:56, Russell Standish a écrit :
> > On Wed, Jun 07, 2006 at 03:56:32PM +0200, Quentin Anciaux wrote: >> >> 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) > > No - halting programs are a subset of N, but there are uncountably > infinite non-halting ones. > > (Assuming we identify all programs without taking the non-read bits > into account). Of course Humpty-Dumpty said, about definitions, that it all depends on who is the master :), but it is against all usage to qualify as digital machine or program something which is not finite or finitely describable. All the teleportation thought experiment where based on the fact that we assume, when assuming comp, that our current local description can be put on some finite disk or something. Especially in our context it would be misleading to generalize the notion of program to infinite one (it can be done but it is another chapter and it can be done mathematically only if we grasp the theory of finite programs and machines before. Actually, many computer scientists call some universal machine "infinite" (although they are finite!!!), but this is just for opposing them to *bounded* automata (which are "more" finite if you want, a universal machine can always ask for some more memory supply. A bounded automate cannot). In Marvin Minsky's cute book "finite and infinite machines", the infinite machines are finite in the usual sense of the word. After people understands clearly what is going on with the diagonalization, it will be easy to define what is a universal machine, and why it is something finite, despite the perhaps misleading idea of Turing's "infinite" (but mostly empty at all time) rubber. So halting and non halting programs are countable. Infinite machine like Nielsen's and Calude's one belongs to a quite different chapter (they will still obey to G and G*, but then, for proving this, much more sophisticated recursion-theory tools are needed, and they presuppose a complete understanding of the finite machine case. Your "definition" can be used in the comp-weaker philosophy, which is, by ordinary standard, a non-comp philosophy, except that they can be lobian or self-referentially correc, and in that case they are still obeying to G and G*. 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 [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~----------~----~----~----~------~----~------~--~---
