AOH :: TURING.TXT Is the Universe "computable?"
```

Is the universe computable?

IT IS an ancient paradox that the rules of nature are simple but the
world itself is complex.  The universe is populated by a rich variety
of physical forms.  Yet whether they are galaxies, clouds or bacteria,
these forms are generated and sculpted by the same underlying laws.

Fast computers have led to a revived interest in the old questions of
complexity.  An institute for complex systems has recently been set up
in Santa Fe, New Mexico.  Mathematicians, physicists and computer
scientists pondering complexity have been led to make speculations
that once lay in the province of philosophers and mystics.  Although
it is mainly concerned with physical things, complexity theory has
been applied to social and economic systems too.

At the heart of these studies is the assumption that a general-purpose
computer can, in principle, simulate any real-life system.  This
assumption is connected with a widely accepted conjecture about
computers which goes under the name of the Church-Turing thesis, named
after two mathematicians, Alonzo Church and Alan Turing, who helped
lay the logical foundations of computing in the 1930s.

Alan Turing is justly famous in England for cracking the German
"Enigma" code during the second world war.  But scientists everywhere
remember him better for his invention of the "Turing machine", a
hypothetical device for performing mathematics mechanically which is
the conceptual forerunner of modern all-purpose computers.  Turing
envisaged a machine rather like a typewriter printing symbols on to a
paper tape of infinite length.  The function of the machine was simply
to move the tape back and forth, type new symbols on it and erase
existing ones, according to a well-defined set of rules.

In essence, a Turing machine is a procedure for converting one string
of symbols into another.  In spite of its simplicity, it is easy to
see that it can perform mathematical operations.  For example, the
computation "2+2=4" can be performed merely by applying a rule that
converts the string of symbols "2+2" into the symbol "4".  What is
perhaps more surprising is that (according to the Church-Turing
thesis) the same simple machine can perform mathematics of any degree
of complexity: anything that is computable at all is computable by a
Turing machine.  What matters is not the physical form a Turing
machine might take but the notion of computability--that a purely
mechanical device can, by following a systematic procedure, perform
what are normally regarded as "mental" manipulations.  Real computers
are not built like typewriters; they are electronic machines.  But the
logic of their operation is the same as that of a Turing machine.

In a paper published in 1937 Turing adapted the work of a philosopher,
Bertrand Russell, and a logician, Kurt Godel, to demonstrate that
there are mathematical operations which are non-computable--ie, which
cannot be performed by any Turing machine.  This immediately raised
some profound questions.  Is the human brain a Turing machine?  If so,
how can people make judgments about something (ie, non-computable
mathematics) which is not accessible to a Turing machine?  If not,
does this imply that the brain is more than a mere machine?  There are
even more baffling possibilities.  Dr Roger Penrose, a mathematician
at Oxford University, argues in a forthcoming book that the brain can
compute things which a Turing machine cannot, by somehow harnessing
quantum-mechanical processes.  If so, the standard version of the
Church-Turing thesis would be false: some things would be computable
without being Turing-computable.

mathematics and the physical world.  At the core of physical science
is the assumption that nature conforms to certain mathematical laws,
such as Newton's inverse square law of gravitation.  The reason why
science works is that the real world can be modelled using such
computable mathematics.  When people's mental faculties become
strained, they can enlist the help of computers--Turing machines--and
thereby tackle problems of ever greater complexity.  But how can you
be sure that nature always avails itself of computable mathematics?
What if some laws of nature are non-computable?

This disturbing prospect has been discussed by Dr Robert Geroch of the
University of Chicago and Dr James Hartle of the University of
California at Santa Barbara.  They attempt to work out the effects of
quantum mechanics on the shape of space, an arcane subject known as
quantum cosmology.  The mathematics used in such sums--which involve
considering all possible trajectories of particles and all possible
topologies (ie, shapes of space)--may be intrinsically non-computable.
The idea raises some points of principle about the limits of what can
be known about the physical world.  If it should turn out that
mathematics which is not Turing-computable holds sway the power of
science could be seriously curtailed.

Despite such recent imponderable hiccoughs, most scientists continue
to believe that nature can be simulated by a Turing machine to an
unlimited level of complexity and detail.  According to this idea, the
phenomena of nature are so analogous to computational processes that
there is no real difference between what a computer does and what
nature does.  Dr David Deutsch of Oxford University points out that
this implies something profound about the physical world.  Any actual
computer, whatever its design, has to work within the laws of hysics.
So what is computable is dictated by the structure of the physical
world.  A simple example of this is the size and age of the universe.
One limit to the size (and thus the power) of computers is the amount
of matter in the universe out of which computers could be fashioned.
Similarly, the duration of the universe sets an ultimate limit to the
length of calculations (unless, as some cosmologists think, the
universe in its final moments would shrink so small so fast that an
infinite number of calculations could be squeezed in).

It is taken for granted that simple Turing-computable operations,
which include arithmetic and algebra, apply to the real world of
dollars and sheep.  (Though they apply only as approximations: in the
real world, the answer to the child's sum "If one television costs 100
[pound sterling], how much do 100 televisions cost?"  Is not 10,000
[pound sterling].  Anybody buying that many would get a discount.)
But the fact that these operations apply at all is fortuitous.  It is
possible to imagine a hypothetical universe in which the physical laws
are so different that operations (such as addition) which are regarded
as computable are non-computable, and vice versa.  The fact that they
are in fact computable depends, for one thing, on the stability of
electrons.  If electrons behaved as wildly as hurricanes--or
multiplied as uncontrollably as rabbits--it would be impossible to
build the sort of on-off circuits that can be used to do arithmetic.

which the laws of physics render computable can also be used to encode
those laws in a simple and elegant fashion.  There is thus a crucial
self-consistency in which physics and computable mathematics mutually
support each other.  Mathematicians have proved that there are far
more non-computable functions than there are computable ones.  It is
lucky that the ones needed to apply most of physics seem to be
computable--so far.

Call THC BBS: +1 604 361 1464 HST   1:340/26   Over 6,200 Text Files!
"Reach for the edges of your mind"

```

The entire AOH site is optimized to look best in Firefox® 3 on a widescreen monitor (1440x900 or better).