> From hpm.domain.name.hidden Tue Feb 13 10:49:14 2001
> Subject: Re: Algorithmic TOEs vs Nonalgorithmic TOEs
>
> juergen.domain.name.hidden:
> > This constructive notion of formal describability is less restrictive
> > than the traditional notion of computability, mainly because we do not
> > insist on the existence of a halting program that computes an upper
> > bound of the convergence time of p's n-th output bit. Formal
> > describability thus pushes constructivism to the extreme, barely
> > avoiding the nonconstructivism embodied by even less restrictive
> > concepts of describability.
>
> It certainly tests the limits, since there's in principle no way of
> knowing in general at any time whether a particular bit of the answer
> on the tape is yet the "final answer".
Sure. Still, each bit eventually stabilizes forever. Hence the entire
bit sequence is constructively describable, and thus a potential universe
history that we may not ignore - it might be ours.
Example 1.1 [Pseudorandom universe] Let x be an infinite sequence
of finite bitstrings x^1,x^2,... representing the history of
some discrete universe, where x^k represents the state of the
universe at discrete time step k, and x^1 the "Big Bang" (compare
http://www.idsia.ch/~juergen/everything/node1.html ). Suppose there is
a finite algorithm A that computes x^{k+1} (k \geq 1) from x^{k} and
additional information noise^k (this may require numerous computational
steps of A, that is, "local" time of the universe may run comparatively
slowly). Assume that noise^k is not truly random but calculated by
invoking a finite pseudorandom generator subroutine. Then x is describable
because it has a finite constructive description.
Example 2.1 [Pseudorandom universe based on halting problem] Let x
be a universe history in the style above. Suppose its pseudorandom
generator's n-th output bit PRG(n) is 1 if the n-th program of an ordered
list of all possible programs halts, and 0 otherwise. Since PRG(n) is
describable, x is too. But there is no halting algorithm computing
PRG(n) for all n, otherwise the halting problem would be solvable,
which it is not. Hence in general there is no computer that outputs
x and only x without ever editing some previously computed history:
http://rapa.idsia.ch/~juergen/toesv2/node7.html
> I see how you could compute Omega: both create and run all Turing
> machines in a diagonalized way, and each time one halts, increase the
> approximation of the halting probability by the appropriate amount.
> But you'd never be sure of even bits near the front, because some
> running small machines might halt anytime, altering those early bits.
Sure. But each bit of Omega will eventually stabilize forever. Omega is
actually not so bad as it is enumerable - you won't even need a GTM
for it, you can compute it on an EOM. GTMs are required, however, for
constructively describable numbers even worse than Omega. See Theorem
3.3:
http://rapa.idsia.ch/~juergen/toesv2/node14.html
> > ... Machines with real-valued registers ...
> > This does not lead outside the GTM realm as long as the indefinitely
> > growing register contents are finite for each finite time step.
>
> Well, I was thinking they would have operations like reciprocal (or
> maybe 1/(x+1) to limit the range) which could instantly generate
> non-terminating expansions. More interestingly they might include
> transcendental operations to generate non-repeating expansions.
> Hey, they could even have the "Omega" operation, which loads
> a register with Omega, all bits finalized.
>
> That certainly beats GTMs.
Check out analytic TMs (Hotz, Vierke and Schieffer,
1995) and R-Machines (Blum, Shub, Smale, 1989):
http://rapa.idsia.ch/~juergen/toesv2/node47.html The alphabet of such TMs
is indeed real-valued instead of binary. This is beyond constructivism
though. GTMs are at the extreme end of the constructive spectrum.
They are beaten by nonconstructive devices only.
But stuff describable by nonconstructive devices only does not even exist.
Does it?
Received on Tue Feb 13 2001 - 05:19:51 PST