Incomputability, Undecidability
and Nondeterminism: from
formal systems to human
minds
Ponte di Legno, 30-12-2003
Filippo Cacace
Università Campus Biomedico, Roma
[email protected]
This presentation is based on
the work by S. Barry Cooper
and Piergiorgio Odifreddi
See:
Incomputability in Nature
unpublished manuscript, 2001
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
2
The questions we want to ask
1.
Does incomputability occur in Nature?
2.
Is a theory of incomputability useful for our
description of the Universe?
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
3
Objections to incomputability
in Physics
–
Despite the development of the mathematical
theory of computability in the 30s (Godel, Turing,
Post, Kleene) one is still left with uncertainty as
to how it applies to the real world
– How would uncomputability be distinguishable
from theoretically computable but very complex
phenomena?
– If the Universe has a discrete and finite model
incomputability does not have any relevance in
its description
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
4
Objections to incomputability
in Physics (2)
– At a purely intuitive level, one has a seemingly

unproblematic model of a deterministic, even
mechanical, Universe
– Incomputability can be incorporated in the
particular form of randomness (for example
quantum indeterminacy) without any need for any
theory of incomputability
Conclusion: the origins of incomputabilty in
mathematics may be theoretical, but they play no
role in physics
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
5
Birth of incomputability theory:
Turing Theorem
"There is no effective procedure (algorithm) for
deciding whether or not a generic program ever
halts"
Proof. A computer
program is a binary string, that is, a natural
number (we include the input for the program in the program
itself). We can list programs in ascending order. For each
program we write the output:
Number
Program
Output
1
p1
r1
2
p2
r2
…
…
…
ri is computed by pi. If the program does not halt, ri =0
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
6
Turing Theorem (2)
rij is the j-th digit of ri.
Now consider the real r*:
r*=0.(r11+1)(r22+1)(r33+1)…
(i.e. if r1=0.4923…,r2=0.1135…, r3=0.98712, then r*=0.528…)
r* cannot be in the list (since is different from any other ri), thus it
is not computable. •
Why we cannot compute r*? One could take the i-th
program, run it, take the i-th digit of its output and
then add 1, thus obtaining the i-th digit of r*.
The problem is that you cannot know whether or not
the i-th program ever halts or outputs a n-th digit:
you can just sit there and wait…
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
7
Turing (1936)  Gödel (1931)
"There is no formal axiomatic system from which all
mathematical truth can be proved"
Proof.
If we had a complete axiomatic system for mathematics
(that is, a system where each true proposition is a provable
theorem) we could run through all possible proofs until we find
a proof that a given program halts, or find a proof that it never
halts. We could therefore decide if any computer program halts.
Since we can't do this (Turing theorem) no formal axiomatic
sysem can be complete. •
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
8
Incomputable sets




The incomputability of real numbers is equivalent to the
incomputability of sets of integers. Such sets are called
recursively enumerable sets (or computably enumerable
sets)
Most "incomputable" sets come with descriptions which
can be tied in closely to diagonalising techniques
For example, all incomputable sets of natural numbers are
solutions to diophantine equations, but in order to
construct such a set, you must use diagonalising
techniques
The lack of "natural" examples of incomputable sets has
been used as an argument against being interested in such
things
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
9
The search for "overt"
incomputability in phisycs


The most straightforward approach would be to
take mathematical equations known to accurately
describe some natural phenomenon, and to
extract solutions exhibiting incomputability in
some generally convincing form
There are a few proposals that illustrate
incomputability which emerges in "natural
mathematics"
see for example:
M.B. Pour-El and J.J. Richards, Computability in Analysis and
Physics, Springer-Verlag, 1989
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
10
The search for "overt"
incomputability in phisycs

Despite these proposals, sceptics find plenty of
scope for arguing that the mathematics involved
is not typical, of for throwing doubt on the role of
incomputability in it.

Moreover, there can e quite plausible obstacles to
overtness. For instance, there may be
mathematical constraints on what
incomputabilities can be described
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
11
What is missing in our
description of the Universe?


Key element in many controversies: interaction
between the local and the global, and among
different levels of descriptions.
There are breakdowns in the reductive structures
commonly relied on in science
Examples:
– quantum wave reduction and associated nonlocality
– reductive nature of evolution
– origins and exact nature of consciousness
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
12

Traditional reductions are no longer adequate

Example: rushing stream
– Local dynamics based on a lower level description
are well understood
– The continually evolving forms on the stream
surface seem to depend on globally emerging
relationships not derivable from local analysis
– The form of the streams constrains the movement
of the molecules of water, while at the same time
being traceable back to those same movements
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
13
A mathematical analogy

A relation is definable from some other
relations/functions on a given domain if it can be
described in terms of those relations/functions
Example: the set  of even integers is definable from
+ within the set  of integers via the formula:
x    (y) ( y + y = x ).
– + is observable and can be algorithmically captured
– But then, standing back from the structure (,+), we
observe something global:  seems to fall into two
distinct parts, with specific properties.
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
14
A mathematical analogy

dynamic flow of water
molecules


dynamics of molecules are
known and computable
global form of the stream

global form is connected
to laws of dynamics but it
is hard to deduce its
properties from the laws




dynamic flow into the
structure: applications of
the form m+n to integers m, n
addition can be computed
appereance of two sets:
even ad odd numbers
properties of these sets
require further analysis
For example, odd numbers flow into
E, but numbers within E never
get out of it. E is maximal subset
having this property
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
15
… this is only a basic metaphor for other
ways in which more or less unexpected
gloabal characteristics of strucutres
emerge quite deterministically from local
infrastructure
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
16
Does the Universe has a
discrete model?



The physical world is representable in a
discretized way (in terms of its quantum
structure), but it does not follow that the
mathematics needed is correspondingly discrete
Much of applied mathematics seems dependent
on limiting processes and descriptions in terms
of real numbers
Non linear phenomena imply that one cannot
describe complex environments within a fixed
level of approximation
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
17



It seems more likely that the observed
discreteness is something imposed by natural
laws on an underlying indiscrete mathematical
model
Even with a finite model, the algorithmic content
associated with natural processes is very
different from a finite, discrete model in that it
entails uncompleted infinities
Real numbers in the form of uncompleted
infinites feed into physical reality, and determine
a mathematical model which is not discrete
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
18
The Universe is a Turing
machine with oracles!




To overcome the shortcomings of discrete
models Turing introduced machines with oracles
An oracle is a (possibly infinite) set of natural
numbers
In Turing machines with oracles (TMO), the
program can ask wether or not a specific number
is in the set, by calling a special function
Essentially, TMO are capable of working with real
numbers, and generate a structure describable in
terms of computale relations over real numbers
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
19
Why real numbers are not TM
computable?

In the proof of Turing Theorem we have built an
incomputable real by means of diagonalisation, a
technique that does not have an obvious
physical counterpart

The incomputability of reals, however, is not
generally due to "diagonalisable" situations:
1. All real numbers are derivable as the limit of a
sequence of computable numbers (rational
numbers)
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
20
2. Even if one limits oneself to computable sequences
of computable numbers, one still gets limiting reals
which are not computable
3. These occurr every time that there is an absence of
a computable modulus of convergence of the
sequence
4. In other words, the link between input and output is
broken: one does not know at any point in the
sequence how close an approximation to the
limiting real is currently being provided
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
21
Incomputable reals = Chaos


The impredictability of association between input
and output is the essence of sensitive
dependence on initial conditions of physical
systems
A matemathical model for chaotic situations
cannot be discrete, and have the sort of
ingredients needed to generate incomputable
elements
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
22
Summary (so far)
– We have provided a preliminary basis for the belief
the the universe is not TM computable
– Its algorithmic content is equivalent to the
structure of computable relations on reals
– The computational counterpart of natural
processes could be Turing machines with oracles;
however certain basic natural processes are not
known to give rise to computable relations
– We now want to show that such phenomena are
modelled via an analysis of invariance and
definability of their basic Turing model
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
23
A model for the Universe



We are considering a scientific presentation of
the Universe via some informative mathematical
structure
We make a comparison among this model and the
Turing Universe
The basic premise of the model is that existence
takes the most general form allowed by
considerations of internal consistence
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
24



Mathematical indications are that a large amount if
information content is needed for the emergence of
anything like a classical Universe of well-defined
individual objects
Such a Universe is rigid, in the sense that it has no
non-trivial automorphism leaving its properties
unchanged
Recent mathematical results suggest that the
Turing Universe (the structure of computable
relations on reals) is not completely rigid: it has a
certain degree of flexibility, even if there are
relatively few (at most countably many) Turing
automorphisms
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
25
Basic structure of matter



Mathematical indications are that a low level of
information content goes with nonrigidity and
lack of Turing-invariant individuals
The correspondent predition for the Universe
would be that its most basic components may
materialise ambigously (lack of definability)
The prediction is confirmed by classic
experiments on subatomic particles, quantum
vacuum, etc.
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
26
Nonlocality



Elaborating such low level of information at levels
of Turing universe at which rigidity sets in will
produce new information content corresponding
to a Turing invariant element
The prediction is that there is a level of material
existence which does not display the ambiguities
of the quantum level, and whose interaction with
the quantum level have the effect of removing
such ambiguity (collapse of wave function)
Since there is no obvios mathematical reason
why quantum ambiguity should remain locally
constrained, non-locality may appear in the
collapse
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
27
Nonlocality (2)
The way in which definability asserts itself in the
Turing universe is not kwown to be computable,
which would explain the difficulties in predicting
exactly how such a collapse might materialise in
practice, and the apparent randomness involved
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
28
Elementary particles



One can only speculate about the origins of
subatomic structure
One guess is that when we look at one such
particle we are observing an instantiation of a
relation, defined on some lower level lacking any
sort of observable form
This could be envisaged as a kind of formless
soup of information content out of which emerge
peacks of definability in the form of subatomic
particles
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
29
Origin of physical laws



The conjecture is that there is a parallel between
natural laws and relations definable in an
appropriate fragment of the Turing universe
The prediction is that a Universe with sufficiently
developed information content to replicate the
Turing universe will manifest corresponding material
relations
The early Universe (immediately after the Big
Bang) could not replicate such a fragment, due to
the homogenisation of its information content
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
30
Complex systems



A Turing definable relation does not necessarily
yield a computable relationship with the defining
factors
However, working with relations at a given level
of abstraction, there may well be computable
relationships emerging, which may become the
basis for a new level of investigation
The prediction is that invariant relations can
emerge at higher level, relating to new entities
reducible to one at previous levels
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
31
… to human minds



A sufficiently complex part of the Universe could
parallel the same processes that define basic
relations of the Universe
Such a system could simulate within it
phenomena within the exterior world
Mental processes, while being a microcosm of
the greater universe, do appear to mirror part of
its complexity and hence its capaciy for global
definition
F. Cacace - Incomputability, Undecidability and Nondeterminism - Ponte di Legno, December 2003
32