> From: hpm.domain.name.hidden
> To: everything-list.domain.name.hidden
> Subject: Re: Algorithmic TOEs vs Nonalgorithmic TOEs
> Date: Fri, 9 Feb 2001 19:26:23 EST
>
> juergen.domain.name.hidden:
> > Nobody will ever be able to fully describe anything that is not
> > computable in the limit by a general Turing Machine.
>
> It hasn't been proven that Turing computability is ultimate in
> computability, only its equivalence to other proposed models of
> computability with finite descriptions. It seems unlikely today, but
> tomorrow someone could come up with an organization that can't be
> simulated on a Turing machine.
Much of
http://rapa.idsia.ch/~juergen/toesv2/ is about
things uncomputable on traditional Turing machines. That's why
we need to introduce General Turing Machines or GTMs:
http://rapa.idsia.ch/~juergen/toesv2/node6.html
> Somewhat unsatisfactory possibilities have been around, that
> can do uncomputable things:
>
> Turing machines with various oracles (with a Chaitin's Omega oracle, a
> machine can solve the halting problem and compute many uncomputable
> numbers).
GTMs are indeed the ultimate in computability as they can compute not only
enumerable numbers such as Omega but also certain nonenumerable numbers.
Since "computable" is often used for "computable by a halting program",
let me use "formally describable" for "GTM-computable in the limit",
and cut and paste from
http://rapa.idsia.ch/~juergen/toesv2/node2.html :
An object X is formally describable if a finite amount of information
completely describes X and only X. More to the point, X should be
representable by a possibly infinite bitstring x such that there is a
finite, possibly never halting program p that computes x and nothing but
x in a way that modifies each output bit at most finitely many times; that
is, each finite beginning of x eventually converges and ceases to change.
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.
> Machines with true real-valued registers. The registers would be
> initialized in a finite way, say to 0, but operations could produce
> register contents corresponding to infinite expansions. I think there
> are "algorithms", like the sieve of Erastothenes, on such infinite
> binary expansions, able to do work in single steps that would take
> Turing machines forever. Halting-type problems can be solved by
> computing all possible cases along the expansion, then doing a
> zero/nonzero test on the final answer, to check for the presence or
> absence of a single bit anywhere.
This does not lead outside the GTM realm as long as the indefinitely
growing register contents are finite for each finite time step.
You are implicitly referring to "weak decidability". Traditionally,
decidability of some problem class implies there is a halting algorithm
that prints out the answer, given a problem from the class. We relax
the notion of decidability by allowing for infinite computations on EOMs
or GTMs whose answers converge after finite yet possibly unpredictable
time. Essentially, an answer needs to be correct for almost all the
time, and may be incorrect for at most finitely many initial time steps:
http://rapa.idsia.ch/~juergen/toesv2/node9.html
The halting problem is weakly decidable. So is the problem of deciding
whether number theory is consistent. After finite time (but you won't know
when) you'll have a correct answer that won't change ever. Interestingly,
there are problems that are not weakly decidable (Theorem 2.1).
Algorithmic TOEs are about universes describable via GTMs, and
probabilities computable in the limit by GTMs. Nonalgorithmic TOEs are
something else, something beyond describability.
Received on Mon Feb 12 2001 - 05:12:18 PST