[FOM] Verifying or Falsifying The Principle of Computational Equivalence
kovasb at wolfram.com
Thu Nov 1 13:13:44 EDT 2007
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
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
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
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.
More information about the FOM