What does one make of the immense body of mathematics based on infinite structures ? The universe may be potentially infinite. Thus questions about whether a Turing Machine
(TM ) will halt can be meaningful without reference to the completed infinite. (TM s are a special class of computer that have unlimited storage and that can execute any mathematical algorithm with the appropriate program.) This is a question of whether an event will ever occur in an indefinite future.
Every initial segment of a potentially infinite universe is potentially empirically accessible to us. Questions about all these segments may be meaningful. To say a TM does not halt is meaningful because if it does halt we (or our distant ancestors) may eventually know about it.
Most of mathematics that deals with the infinite can be interpreted as dealing with the potentially infinite. For example the question of whether a species will have an infinite chain of descendant species can be defined in a way that requires quantification over the reals . There is no single event that decides this question but it is still meaningful and interesting in a potentially infinite universe. It is determined by a recursively enumerable set of events that can be listed by a computer. Some questions such as the Continuum Hypothesis
(see Appendix 
on page
) cannot be. I do not think
such questions have any absolute meaning. They are questions
about formal system s which are within a
particular system true, false or undecidable.
To understand in more detail how to develop conventional
mathematics along these lines we revive the old idea of the
`
' quantifier. This can replace both the universal and existential
quantifiers over the integers: 
is true if and only if 
is true for some infinite subset of the integers. This
is equivalent to saying that some particular TM has an infinite
number of outputs.
This can be generalized to provide an interpretation of the arithmetical sets of integers (those definable with a finite number of quantifiers ranging over the integers). To do so we use the concept of a nondeterministic TM . Here nondeterministic does not refer to probabilistic behavior. A nondeterministic TM is completely deterministic in its behavior. However, instead of executing a single program, it executes one or more (up to a recursively enumerable set) programs.
Any arithmetical set of integers can be defined by a succession
of a finite number of 
quantifiers: 
. This in
turn is interpretable as some statement about a nondeterministic TM
. For two quantifiers, the equivalent statement is that a TM
has an infinite number
of outputs, such that an infinite subset of these are the
Gödel numbers of TM s that in turn have an infinite number of
outputs. This is equivalent to a statement about a single
nondeterministic TM , since we can easily program such a machine to
simulate all the TM s that 
outputs. This result can be generalized to any finite
number of `
'
quantifiers.
Generalizing further one can also define the hyperarithmetical sets of integers
as properties of nondeterministic TM s.
We can go a little further. To define the set of all hyperarithmetical sets of integers or equivalently all recursive ordinals
requires quantification over the reals. See Appendix on page if these terms are not
familiar. Yet this set also has a natural interpretation in terms
of nondeterministic TM s. To show this we introduce a variation on
the notion of well foundedness . Program a nondeterministic TM to do the
following given the Gödel number of
some other TM (
) as
input. Simulate 
and for
every value that 
outputs treat this as a the Gödel number of another TM .
Simulate this machine just as 
is simulated, so each of its outputs is interpreted as
the Gödel number of another TM . Repeat this process for all
outputs of all machines simulated. A path through this tree of
simulations is defined to be a sequence of Gödel numbers of TM
s. The first element of the sequence is 
, the second is an output of 
, the third is the output from the second
element in the sequence, the fourth and output from the third etc.
is well founded if
every path is finite. The set of all recursive ordinals is
recursive in the set of well founded TM s. This is not surprising
since the definition of well founded TM is close to the definition
of a recursive ordinal.
At least this initial fragment of the hierarchy of real numbers has a natural interpretation as properties of TM s.
What is the advantage of analyzing mathematics in this way and is this mathematics, even interpreted as properties of TM s, relevant to anything at all? Understanding the mathematics as properties of TM s offers the possibility of adding an experimental element to the study of logic. One can write programs of the type just discussed and observe their behavior. This can make it easier to gain insight into this area of mathematics. Something like this has happened. Until recently nonlinear differential equations were, for the most part, ignored as being too complex to understand. Once researchers started playing with simulations, a new branch of mathematics, Chaos theory , was created. Chaos theory is only possible because one can simulate complex systems and observe their behavior.
We know mathematics that requires quantification over infinite sets is useful because it can make it easier to decide practical questions. However, if there are no infinite sets, does this mathematics have a meaning and use in its own right as opposed to being an aid to decide lower level questions? Nondeterministic TM 's are similar to the most important process on earth: biological evolution . (At least this is true if biological processes only has access to finite computation.) If we identify a species with a single TM then the question of well foundedness for biological evolution is the question will any species have an infinite chain (the second element of the chain is a descendant of the first, the third a descendant of the second, etc.) of descendant species.
Consider that nondeterministic processes are not subject to the limitations of Gödel 's incompleteness theorem . As long as the number of paths of evolution that you follow increases without limit, there is nothing to prevent one particular path from ultimately solving the halting problem for every TM using a chain of mathematical systems each of which proves the consistency of the previous one. This suggests that thinking in terms of nondeterministic processes
may be helpful in creating mathematics and that the resulting mathematics is the mathematics of creativity.
| home | consulting | videos | book | QM FAQ | contact |