[FOM] Principle of Computational Equivalence
kovasb at wolfram.com
Mon Nov 19 16:06:50 EST 2007
Bill Taylor wrote:
> As it relates to theoretical computational devices, this is surely
> a rephrasing of the result that "there exist Universal Turing
> (or their equivalents in other computational contexts).
I've seen this line of thinking raised before, so I will try to
explain how the PCE goes beyond the Church-Turing thesis (CTT) in its
content as well as its implications.
The statement of the PCE is a very compact way of relating three
separate ideas. Essentially there are three kinds of equivalences
that the PCE asserts or assumes, each of which goes beyond any other
theoretical framework or principle:
-- Equivalence between complexity of the *behavior* of the system, as
judged by methods of analysis and perception, to the computational
properties of the system
The PCE relates how a system appears to behave to a more abstract
quality that Wolfram calls "computational sophistication", which is
not quite the same thing as universality but has other concrete
implications described below.
The CTT doesn't make any comment on the behavior of systems (only on
their theoretical capabilities), and therefore for example is silent
on the issue of if for example rule 110 and the 2,3 machine should be
universal, given the empirical fact of their complex behavior.
-- Equivalence between different computations
Whereas the CTT talks about the equivalence of systems, the PCE talks
about the equivalence of specific computations performed by systems.
In effect, it is a much stronger statement. A universal machine may
perform a simple computation, or it may perform a sophisticated
computation, depending on the program it is running.
The PCE is concerned with the sophisticated computations. And it
claims that one sophisticated computation is equivalent to the others
in its sophistication.
A concrete consequence, not predicted by any other framework, is
these "sophisticated" computations cannot be run more efficiently by
other, presumably more sophisticated computations. So the most
efficient way to evolve rule 30 is just by running the rule itself,
rather than some other system that is being more clever in how it
computes. (with the exception of say linear-time speedups from the
use of bigger lookuptables etc)
(in the language of computation theory, the PCE says that the most
efficient 'effective procedure' for determining the halting of a
system engaged in sophisticated computation is to run the system itself)
This phenomena of computational irreducibility is important, because
it implies that models of nature that seek to reproduce complex
phenomena must themselves be capable of doing sophisticated
computation. This is a theoretical justification for why computers
are fundamentally necessary, as opposed to just compensating for a
lack of cleverness.
It is also important even in the scientific study of simple programs,
since it implies that closed-form solutions to the behavior of these
systems is extremely rare, and that experimental methods are really
the only way to ascertain their behavior.
-- Equivalence between computational processes and physical processes
The CTT is not a statement about the physical universe, but rather a
statement about human ability to come up with "procedures".
The idea that the universe is computable does not come for free from
the CTT. There could easily exist non-computable processes in the
universe, yet we as humans could never have access to them or wrap
our minds around them to the extent needed to falsify the CTT.
Nevertheless the idea on its own is nowadays commonplace, as so this
aspect PCE is not original in that respect, though it should be noted
that this popular belief does not have an origin in any real principle.
The PCE says more than just that the universe is computable though.
It also claims that the origin of complexity in physical processes is
in fact their computational sophistication. The PCE claims that in
effect, that the natural systems do not have a fundamentally
different character than computational systems, and therefore the
same phenomena and principles that apply in one world apply to the
other. Just as phenomena first discovered in cellular automata are
later revealed in turing machines, so too phenomena from these more
abstract systems will appear in their physical cousins.
Clearly many aspects of the PCE are subject to debate, and there is
no shortage of people who strongly disagree with certain
implications. For example many in the computational complexity
community and the complex natural systems community take issue with
the PCE's marginalization of complexity classes. The wide variety of
(often contradictory) opinions on the PCE I think is also an
indicator that it goes beyond the safe territory of 70 year old
More information about the FOM