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 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:57:55 PDT