[FOM] Verifying or Falsifying The Principle of Computational Equivalence

[Kovas Boguta]

There have been some recent messages speculating on what it would take to 
falsify the PCE.

The PCE is not a mathematical conjecture, and cannot be proven or 
disproven by a single theorem or counterexample. It is instead a statement 
about what will typically occur in 'practice' with computational systems, 
and therefore its verification or falsification is primarily an
  experimental matter.

It is well known that there are a class of systems that seem to contradict 
the spirit of the PCE, due to being capable of exhibiting complexity yet 
failing to be universal. In fact, Wolfram gives perhaps the minimal such 
system -- the first primitive recursive function to show complex behavior 
-- on

http://www.wolframscience.com/nksonline/page-907b-text

There are two important points to keep in mind when considering the 
significance of such systems.

The first is that the PCE is not a statement about systems, but rather a 
statement about the concrete computations performed by systems. 
Understanding how these two worlds relate to each other is an open 
question. Statements about universality are ultimately derivative from the 
PCE, and we do not yet understand their nature.

Nevertheless, the PCE does seem to imply that most systems that show 
complex behavior will turn out to the universal. The validity of this 
prediction then hinges on the interpretation of "most". Is it 90%? 
99.999%? My second point concerns how this qualitative measure should be 
judged.

One issue with the theoretical study of computation is that invariably 
much research effort will be expended resolving "corner cases". And if one 
defines "most" in terms of the number of publications on certain topics, 
one's intuition will be skewed against the PCE, due the intricate web of 
technical details that may keep systems from "full" universality.

An alternative population of systems can be generated by enumerating 
simple programs, and I believe this is the correct way to measure the 
success of the PCE. Their population is large and diverse, and may be 
systematically studied. Most importantly, their behavior is not engineered 
by humans, and therefore can be understood as an authentic representation 
of what is or is not common in the computational universe.