Re: Algorithmic TOEs vs Nonalgorithmic TOEs

From: <hpm.domain.name.hidden>
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.

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).

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.
Received on Fri Feb 09 2001 - 16:30:51 PST