re: noncomputability

From: Mitchell J Porter (mjporter@U.Arizona.EDU)
Date: Thu Jul 26 2001 - 09:25:49 MDT

> I think that really boils down to a belief that the only way a
> mental process could be uncomputable is if it arises from an
> uncomputable physical process. (Maybe so, and if so then the
> paragraph I wrote that you quoted above, if not nonsense, is yet
> incorrect.)

I know two ways to implement noncomputability without having
a new, fundamental, noncomputable process. One is to use an
infinite chain of baby universes and wormholes: if you want to
know whether a function halts, you just start calculating it,
putting the outcome of each step in the next baby universe in
the chain, along with something that will send a signal back up
the wormhole chain if the computation does indeed halt. (See
part 4 for something like this.) The other way is to use time
loops. I don't know how this works, but Penrose cites David
Deutsch, saying that you can get noncomputability out of a
quantum computer in a closed timelike curve. (It must somehow
be a result of the constraints created by the requirement of
global causal consistency - perhaps, by tweaking the boundary
conditions, you force the time loop to either perform the
computation and stop, or protest that it never stops - but I
don't know the details.)

In both cases, while you only have Turing-computable operations
locally, you get to violate the usual 'structural' assumption
of finite sequential time. So to do the noncomputable you
need non-Turing physical processes or non-Turing temporal

Perhaps the bottom line is that computation is as much a
concept of physics as well as one of mathematics, because
it involves causality.

This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:00:37 MDT