Juergen wrote also (Sorry for cutting my comments)
>Here is the best you can achieve with a dovetailer. You can
>extract representations of all the countably many computable reals.
>How? Systematically enumerate all possible input strings, viewing them as
>starts of programs to be executed in dovetail fashion. This excludes
>many strings that cannot be input programs because one of their prefixes
>already is a self-delimiting program that will never request additional
>bits. Some input strings, however, are valid, finite, possibly
>nonhalting programs (such as the algorithm computing the decimal expansion
>of 1/3). They generate possibly infinite objects (such as 0.33333...).
>Make a list containing all current programs or program prefixes.
>Update the list whenever one of its elements requests a new bit. This
>will eventually give you finite representations of each computable real.
I doubt that. The set of computable real is not recursively enumerable.
But OK in the limit. It is recursive in the halting set ...
>But your own so-called "dovetailer" essentially is
>the extremely inefficient algorithm called ALPHABET in
>http://rapa.idsia.ch/~juergen/toesv2/node27.html . ALPHABET simply
>lists all bitstrings ordered by size and separated by blanks. Note that
>countably many steps are insufficient for ALPHABET to print any infinite
>string! So ALPHABET clearly is the wrong approach when it comes to
>generating all computable universes.
DU generates all the infinite strings. It generates the non stopping
computations including those using real as oracle. It makes Zig-Zag
on all "Brouwer's Fan".
I don't remember having propose an algorithm for the UD (apart from
the explicative specification). In my 1995 report I write an efficient
one, which also "quasi-compute" Chaitin OMEGA number.
As Gilles Levy pointed out the efficiency of the UD is not relevant, for
the sharing space-time emerges from the statistics of the whole set
of finite and infinite computationnal histories, from the first person
point of view or first person plural point of view in the case of
bifurcation of deep computational histories shared by many.
As I said in my preceeding post it could be that the ``natural universal
dovetelair" is a quantum one. But still, it is generated by the classical
dovetailer. It just mean that its way of multiplying and entangling long
histories makes these stories winning from the first person statistical
anticipation point of view.
Now you know that when the classical UTM simulates the
quantum one there is an exponential slow-down. The invariance lemma
entails we cannot be aware of that !
No doubt the Great Programmer, as you call it, is rather stupid, and
trying to speed up a little will not help.
>From the "inside" point of view, it is what most machines observe and
anticipate relatively to their most probable computational histories,
among all possible one (including non stopping one), which counts.
>Once more: The concepts of dovetailing and continuum are incompatible!
Yes. In a trivial sense from a third person point of view. But about
the question "in which computational history am I", well, if I am
a machine, then a priori I can belong to 2^aleph_0 histories.
If you have still a doubt let me explain you my iterated
self-duplication experience WM (from my 1988 paper).
Annihilation at Brussels, reconstitution at Washington (W) and Moscow (M).
The one in Moscow writes M on his t-shirt, and the one in Washington
write W.
Then you come back by plane, each of you!, and do the experience again,
and again, and again ...
Each infinite sequence WMWMMMWWMWMMM... will be generated, although
each of you cannot compress its t-shirt inscription, it just does not
know which will be its computational history among all infinite
sequence of W and M. Most of you will be able, in this setting
to anticipate that you cannot anticipate. This is one exemple of
computational undeterminacy.
Bruno
Received on Sat Jan 27 2001 - 08:20:48 PST