[time 471] Noncomputability

Matti Pitkanen (matpitka@pcu.helsinki.fi)
Fri, 23 Jul 1999 18:49:24 +0300 (EET DST)

Part of Roger Penrose's hypothesis regarding the form
of a final theory is that its dynamics should be
noncomputable. Recall that this simply means that no
Turing machine could reproduce this dynamics in the
output of a calculation. Mathematics already offers
examples of noncomputable sequences whose first few
elements we know, but only because we have hit upon
methods that suffice to identify those particular

[MP] I read Shadows of the Mind and Penrose's comments
on it on some homepage. He left open whether
quantum theory os genuinely non-deterministic or
whether noncomputality gives rise to effective nondeterminism.

I think the basic problem is that
quantum nondeterminism is *not* random! On the
contrary: in quantum jump only states belonging to discrete
set of states are possible. It is extremely difficult to
see how this kind of non-randomness could result from
deterministic but non-calculable dynamics.
In addition one should understand the reduction
probabilities. And the prize for all these feats
would be mystery: we we experience of having free will
despite that free will is not actual!

When looking for noncomputability in physics, Penrose
suggests that quantum gravity with topology change
might be noncomputable, since four-manifolds are
not classifiable, and four-manifolds would interpolate
between the spacelike hypersurfaces at either end
of a sum over histories. This would give us
noncomputable amplitudes, and so noncomputable
transition probabilities.

I have seen this kind of argument somewhere.
One could however consider quite well the possibility
that amplitude is calculable after all. Calculation
need not be done by numerical computing by taking
actually the sum over all histories.

On basis of frustrating personal experiences I do not
believe on the summation over histories:
a purely formal generalization of
Feynmanns sum over histories approach is in question. There
is not guarantee that resulting amplitudes are unitary.
I spend more than seven years trying to make some sense
about summation over spacetime surface idea until I realized
that configuration space geometry is the only possibility
to achieve manifestly unitary theory.

This might be suitable for a noncomputable stochastic
theory, but I wonder if we could go further and have
a deterministic noncomputable theory. In this regard
I find Chaitin's number interesting. Chaitin's number
is the halting probability for a Turing machine,
given certain weightings on initial conditions.
Not only is Chaitin's number noncomputable, it is a
random real, which means that it is statistically
indistinguishable from a random series.

Could the apparent randomness of quantum behavior,
rather than resulting from real (albeit structured)
randomness, be the result of a pseudorandom,
deterministic noncomputable dynamic?


This archive was generated by hypermail 2.0b3 on Sun Oct 17 1999 - 22:36:56 JST