On Sun Jan 21 15:29:39 2001 Bruno Marchal wrote
> There is nothing magical hidden in my reasoning, and I have no doubt
> you will understand it soon or late :-)
> (I surely agree that in some steps I am a little quick ; my
> pedagogical problem is that nobody agrees on which steps are
> easy or difficult).
I think you tend to write too much, not too little. None of your
"pedagogical" examples answers my question though. Let me cut and paste
once more:
You are repeatedly talking about universes generated by a dovetailer. All
these universes obviously must be computable, otherwise the dovetailer
could not compute them. You claim that there is no computable universe
to which we belong, but the very tool you are using generates lots of
universes to which we belong. Can you explain this contradiction?
On Sat Jan 20 15:32:06 2001 Bruno Marchal wrote
> Juergen wrote
> >The infinite computational histories are countable. The continuum is not.
> >The concepts of dovetailing and continuum are incompatible.
>
> But you can write a program which dovetails on the reals !
> I have already explain in the list why there is no contradiction
> with cantor diagonal proof of the non enumerability of the real.
> It is no more astonishing than the existence of a short program
> which generate all the finite string, including those which
> are very long and chaitin incompressible. The trick is to generate
> them *all*.
> ... but the dovetailer generates, for each real, all its
> bigger and bigger prefixes, and that is called traditionnaly,
> generating the real. And the dovetailer do that for each real,
> and so generates all the uncountably many reals.
I am afraid this is nonsense. Obviously I can count the outputs of
your dovetailer. I can count the time steps it consumes. Hence
the dovetailer cannot possibly generate uncountably many things.
You are just generating countably many prefixes of reals, each prefix
being the start of uncountably many reals (most of which do not exist
from any constructive point of view). What you are really generating
is not the reals but countably many representatives of subsets of the
reals, each subset containing uncountably many elements. This has
nothing to do with generating or representing the elements themselves.
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.
Furthermore, each infinite string computable in countable time will
be computed in countable time by an optimal dovetailer like
the one in
http://rapa.idsia.ch/~juergen/toesv2/node28.html
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.
Once more: The concepts of dovetailing and continuum are incompatible!
Juergen
Received on Thu Jan 25 2001 - 05:22:54 PST