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



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 

Reply via email to