TWO YEARS OF STRUGGLE WITH COMPUTATIONAL EQUIVALENCE

Matthew Frank

TWO YEARS OF STRUGGLE WITH COMPUTATIONAL EQUIVALENCE

PCE = "Almost all processes that are not obviously simple can be viewed as computations of equivalent sophistication." [717]

1) We have no substantial formulation of PCE which is either a theorem or a plausible precise conjecture -- hence the struggle.

2) Optimism about closely related topics (e.g. computational irreducibility).

Caveat:  "Almost any statement that can readily be investigated by the traditional methods of mathematical proof will tend to be largely irrelevant to the true PCE."  [727]

A struggle largely by correspondence.

People outside WRI:
John Baldwin
Richard Friedberg
Pradyut Shah
Ben Wieland

People inside WRI:
Jason Cawley
Todd Rowland
Matthew Szudzik [see his forum post]
Stephen Wolfram

WHAT IS A COMPUTATION?

An abstract answer:  something which proceeds by making changes on the basis of local information, in a coherent and synchronized way.

There is enough trouble in the concrete contexts of CAs and TMs.

rule = {{13, 3, 13} -> 12, {6, _, 4} -> 
          15, {10, _, 3 | 11} -> 15, {13, 7, _} -> 
          8, {13, 8, 7} -> 13, {15, 8, _} -> 1, {8, _, _} -> 
          7, {15, 1, _} -> 2, {_, 1, _} -> 1, {1, _, _} -> 
          8, {2 | 4 | 5, _, _} -> 13, {15, 2, _} -> 
          4, {_, 4, 8} -> 4, {_, 4, _} -> 5, {_, 5, _} -> 
          3, {15, 3, _} -> 12, {_, x : (2 | 3 | 8), _} -> 
          x, {_, x : (11 | 12), _} -> x - 1, {11, _, _} -> 
          13, {13, _, 1 | 2 | 3 | 5 | 6 | 10 | 11} -> 
          15, {13, 0, 8} -> 15, {14, _, 6 | 10} -> 
          15, {10, 0 | 9 | 13, 6 | 10} -> 15, {6, _, 6} -> 
          0, {_, _, 10} -> 9, {6 | 10, 15, 9} -> 
          14, {_, 6 | 10, 9 | 14 | 15} -> 10, {_, 6 | 10, _} -> 
          6, {6 | 10, 15, _} -> 13, {13 | 14, _, 9 | 15} -> 
          14, {13 | 14, _, _} -> 13, {_, _, 15} -> 
          15, {_, _, 9 | 14} -> 9, {_, _, _} -> 0}

CellularAutomaton[{(#  /. rule) &, {}, 1}, {{10, 0, 4, 8}, 0}, 
        100]  //  Show[Graphics[Raster[Reverse[1 - #/15]]]] &

PCE FOR PARTICULAR COMPUTATIONS

The strong form of PCE [724] says that every computation is either obviously simple or universal.  (By contrast, the ordinary form says that every computing process is either simple or universal.  The strong form says that the graph on the previous page is universal; the ordinary form says only that the rule on the previous page is universal.)

In particular:
the run of rule 110 on the simplest background should be universal
the CA for the primes (as on the previous page) should be universal

We have no precise statement and no proof of either of these.
The second claim is contrary to my intuition:  the run of the prime-generating CA does not look as complicated as the run of rule 110

UPDATING PROCEDURES

PCE is not about functions or sets.
PCE is about repeated application of some updating procedure to some state, and the history of states that results.
In these terms, PCE states:

For any updating procedure,
either that procedure always yields simple results,
or that procedure can be made to emulate any computation
via an appropriate choice of initial conditions

Many undefined terms:
simple, emulate, appropriate

PONDERING WHAT WE HAVE:
UNIVERSAL TURING MACHINES AND RULE 110

We can give a precise definition of a universal Turing machine.
We can state precisely that Life or rule 110 can emulate any Turing machine.

There are simple translations TM2CA and CA2TM such that:

for any Turing Machine M,
for any input n to the turing machine,

running rule 110 on the initial condition TM2CA(M,n)
and decoding appropriate lines of its evolution by CA2TM
yields M's behavior on input n.

PONDERING WHAT WE DON'T HAVE:
THE LIMITS OF THE RULE 110 EXAMPLE

The rule 110 example does not give us a precise statement of the principle of computational equivalence.

Note:  The rule 110 emulation has exponential slow-down
t steps of Turing machine evolution
require (2^( t)) steps of rule 110 evolution

Q1:  How much slow down is acceptable?
Q2:  What translations between CAs and TMs are acceptable?
Q3:  What does "obviously simple" mean in mathematical terms?

Allowing all recursive functions as "acceptable" or "simple" makes the concept of equivalence trivial.

REFERENCES OUTSIDE NKS

Matthew Cook, forthcoming in Journal of Complex Systems
for proof of universality of rule 110

Bruno Durand and Zsuzsanna Roka,
The Game of Life:  Universality Revisited
for precise statements of universality

Wilfried Sieg (following Turing and Gandy),
Calculations by Man and Machine
for an abstract setting for computation

AN OBJECTION TO PCE FROM THE BOOK

"Structures [in rule 30] always seem to move at the same speed, and so can never interact." [701]

This makes it hard to see how rule 30 could emulate computing systems.

DRAWING CONCLUSIONS WITHOUT PCE?

Some of the book's conclusions require the full force of PCE:

[844] almost every thing has the computational complexity of humans
[785] almost every axiom system encodes the behavior of any system

Other conclusions drawn from PCE - those about possibilities -
would also follow from universality of rule 110
or from universality of other small systems:

[730] digital technology can do anything analog technology can
[841] nano-computers can do anything computers can
[822] human intelligence can be based on simple things
[736] complexity in nature can be based on simple things

COMPUTATIONAL IRREDUCIBILITY [737-750]

Irreducibility = "there can be no way how to predict how a system will behave except by going through almost as many steps of computation as the evolution of the system itself." [739]

Some of the consequences drawn from computational equivalence would follow more directly from computational irreducibility instead:

[750] (explanation of the) illusion of free will
[748] can't always expect a simple formula
  (even if the causes are simple)
[1196] can't always predict systems
  even if you know how they function
[1136] can't always predict consequences of laws--
  whether the law is computational or congressional

A CONJECTURE ON COMPUTATIONAL IRREDUCIBILITY

Let WorstTime(T,n) be the longest time that Turing machine T takes to halt over all inputs of length n on which it does halt.  (See computations of this, pp. 758-764.)

T is reducible if some Turing machine U with the same inputs and outputs has

WorstTime(U,n)/WorstTime(T,n) -> 0 as n -> infinity

Conjecture:  As the number of states grows to infinity, the fraction of reducible Turing machines goes to 0.