[FOM] Physical Theories and Hypercomputation
Dmytro Taranovsky
dmytro at mit.edu
Wed Mar 7 18:30:26 EST 2012
This posting explains the relation between physical theories and
computability.
Physical theories are ordinarily stated in terms of real numbers and
quantities that are reducible to real numbers, such as continuous
functions between (specific) separable metric spaces. Real numbers are
a priori infinite quantities, that is they can store infinite
information, which raises the question as to why the theories tend to be
computable. The answer is that the finite nature of observations
combined with approximate nature of physical theories naturally leads to
continuous time evolution relation. For example, if distance is only
predicted approximately because of (for example) neglection of
corrections from a more accurate unknown theory, it does not appear
relevant whether a predicted non-zero distance is rational or
irrational. A continuous function is recursive in terms of some real
constant. Continuity means that one can create finite approximations to
the theory with arbitrarily high specified quality/precision -- for
example by quantizing space-time and limiting floating point precision
-- and recursiveness allows for these approximations to be (uniformly)
computable.
There are 3 ways in which physical theories can lead to hypercomputation:
* failure of continuity
* non-recursive physical constants
* non-recursive initial conditions
An empirical fact is that in current and past physical theories,
physical constants are either recursive or only predicted approximately
(if predicted at all). This should not be surprising since we do not
know non-recursive natural real numbers (that are natural as real
numbers) or even non-recursive natural continuous functions between real
numbers. Recursiveness in terms of freely choosable (in a certain
range) constants also follows (ordinarily not formally) from the form of
typical theories: A differential equation for the time evolution with
terms that are elementary functions.
Even if the physical constants are non-recursive, then under current
physics, they appear to be a sparse oracle -- and thus worst case time
complexity of the halting problem would remain exponential or worse --
because of their limited number and because of difficulty of arbitrary
precision measurements.
In addition to specifying time evolution, a physical theory may also
partially specify initial conditions, and nonrecursive initial
conditions may allow hypercomputation.
Continuous time evolution may still lead to singularities (unless the
state space is compact), which can be dealt in three ways:
* Modify the theory to prevent singularities. This is the usual
solution since near singularities some values are arbitrarily large and
thus likely imply new physics. However, there is no universal guarantee
that the more accurate theory will not have the same (or some other)
singularity.
* Apply the theory except at singularities and define the transition at
singularities. The result is usually nonrecursive (assuming that
singularities are common enough for a computer to be able to steer
itself into one).
* Prohibit initial conditions that lead to singularities. In some
cases, a theory leads to singularities unless some factors are precisely
canceled out, which potentially requires non-recursive initial
conditions. As to potential hypercomputation, assume that time
evolution as a function of initial conditions is a recursive function up
to a potential singularity. Note that even if for a certain initial
condition, time evolution does not lead to singularity, it may still
approach singularity at a superrecursive speed, which may lead to
superrecursive slowdown of computation of its time evolution. Thus,
there are 2 cases:
- If there is a solution without superrecursive slowdown for computing
approximations, then hypercomputation that is valid for all initial
conditions (that will not lead to singularity) is limited to separation
of disjoint recursively enumerable sets. Separation of disjoint r.e.
sets would not solve the halting problem, but if available efficiently
(for a pair that is universal under polynomial-time reducibility), would
make every recursive predicate computable in polynomial time.
- In the general case, we can do arbitrary hyperarithmetic
computation. This occurs even if we have just 2 degrees of freedom, one
of which can be a constant of motion. For example, for every recursive
omega-consistent theory T, there is a smooth recursive f with all
derivatives recursive such that y'(t) = f(a, y) has a solution that does
not go to infinity at finite t iff 'a' encodes (in a standard way) an
omega model of T (a and y are real numbers and a is constant). For all
T containing ATR_0 with Skolem functions, this allows arbitrary
hyperarithmetic hypercomputation.
With respect to the Standard Model, we do not know (as of March 2012)
whether it is generally consistent (as in singularity-free time
evolution), or inconsistent, or requires special initial conditions, and
if so, whether that can be used for hypercomputation. Furthermore, while
recursive approximations to Standard Model are known (for example,
through lattice gauge theories), it is not known whether they converge
in the limit to theory, and even infinitesimal (as in arbitrarily short
from a fixed starting point) time evolution might be problematic (which
may potentially lead to additional nonrecursiveness).
For theories that allow hypercomputation, hypercomputation -- by its
nature and unlike ordinary predictions -- tends to depend on infinite
precision of certain parts of the theory, and physical theories are
usually approximate. Thus, hypercomputation predictions usually involve
applying the theory fundamentally outside its ordinary domain, so it is
reasonable to be skeptical unless partial hypercomputation or some form
of infinite precision of the theory has been tested. One method that
arguably does not depend on infinite precision is that if a discrete
physical process decays (that is loses frequency) at a sufficiently fast
rate (as a function of the number of past events), this can be used for
(very slow) arbitrary hyperarithmetic hypercomputation regardless of
what the rate is, provided that the process still generates an unlimited
number of events.
The best argument for hypercomputation is based on the physical laws
optimality principle: Physical laws are the best possible. The
optimality principle is related to the anthropic principle, and also to
the widely held view that physical laws are beautiful. Once one is
convinced that it is better to have universe in which nonrecursive
nonrandom processes are possible, one applies the optimality principle
to conclude that nonrecursive nonrandom processes are possible in the
actual universe.
Sincerely,
Dmytro Taranovsky
http://web.mit.edu/dmytro/www/main.htm
More information about the FOM
mailing list