[FOM] Principle of Computational Equivalence

[Kovas Boguta]

Bill Taylor wrote:

> As it relates to theoretical computational devices, this is surely
> a rephrasing of the result that "there exist Universal Turing  
> Machines",
> (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  
theorems.