[FOM] Principle of Computational Equivalence

Bill Taylor W.Taylor at math.canterbury.ac.nz
Wed Nov 14 01:19:22 EST 2007

I have been reading the debates about the universality of the 2-3-TM,
with great interest.  It is too soon for us mere onlookers to make
an informed judgement about it, but it is at least clear that the topic
of universality, so clear-cut in computations at large, is a very
vexed and complex one when concerned with tiny devices, and was given
insufficient elucidation before the matter of any prize was raised.

However, what I chiefly wish to comment on is the so-called
"Principle of Computational Equivalence".

I refer to MathWorld's own definition:-

** Almost all processes that are not obviously simple can be viewed as
** computations of equivalent sophistication

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).

Is this all there is to it?  Have I missed something vital?
If this is IT, then this result has now been known for about 70 years,
so hardly deserves a new name, much less that of a latecomer to the field.

MathWorld goes on:

** More specifically, the principle of computational equivalence says that
** systems found in the natural world can perform computations up to a
** maximal ("universal") level of computational power, and that most
** systems do in fact attain this maximal level of computational power.

Insofar as this is a statement about the real physical world,
to call it a computational principle is somewhat of a category mistake;
along the lines of Lucas' simple-minded interpretation of Godel's theorem
as saying something significant about specifically human ability.
The fact is that physical systems fail to be candidates for universality
(or any other theoretical computational property), as they have neither
the infinite time nor resources that these abstract devices require.

However, let us be generous, and admit that Mother Nature's attempts
at computation can be modelled in some significant way, that allows us
to speak of Universality etc for them.  What does this paraphrase
of the PCE say now?  It appears merely to say, that some natural
computational devices can be modelled as UTMs (modulo those remarks
about infinitudes).  Is this exciting or new?  Well, not new, in that
we already knew (since 1937) that a small part of human understanding
could be seen this way.  Is it exciting that other, sub-human natural
computers can do the same?  Perhaps it IS exciting, but it is still
hardly new, in that the underlying computational theorem (UTMs exist)
will apply anywhere where there is sufficient computational proclivity.

All that now remains are the geographical/biological problems, to sort out
where this holds, and where it doesn't.  An important task, for science.
But again, all of it that seems to be contained in the PCE is the fact
that "UTMs exist".  I can't help feeling that I'm missing something vital.

If I am, will someone please enlighten me.

If I'm not, then one must seriously question Wolfram's motivations
for re-announcing such an old and easy computational result.

Bill Taylor

More information about the FOM mailing list