[FOM] Principle of Computational Equivalence

[Thomas Lord]

Kovas Boguta wrote:
> 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. [....]
>   

If we could relate this back to the question of the 2-3 machine:

If we regard Smith's construction as a description of a class of
physical systems then it describes two (or three) processes,
running concurrently where the first (a tape initializer) communicates
an infinite  amount of information to the second (the 2-3)
and, if a third machine is present (a halting condition decider),
then the second machine communicates an unbounded amount of
information to the third.

*By* the PCE, we should not casually overlook the role of
machine one (initializer) in the overall system.   Specifically, by PCE,
we ought to suspect that there is no more efficient expression
of the initializer, other than to actually run it concurrently with
the 2-3 machine.   The conjunction of the 2-3 with the initializer
is "universal," not the 2-3 alone.

Smith's construction is very cool, of course (if it continues to bear
the challenge of verification).   He has proved something I think is
very interesting (if we overlook halting for a moment although he
is apparently fixing that):

He has proved that you can build a universal system in which
something as simple as the 2-3 is the only component whose
behavior is "unboundedly strict" in previously written values.
That is, in a system that has a Smith-initializer plus a 2-3, the
2-3 machine is the only component capable of writing values to
the tape where the value written is strictly a function of an unbounded
number of values previously written.   Such an "unbounded strictness"
property is a necessary though not sufficient (or is it?) condition
for universality.   Smith's initializer seems to lack the unbounded
strictness property and 2-3 has it, so the 2-3 component serves some
vital role and is indeed remarkably simple.   But, to say it is "universal"
is to overlook the possibility that the 2-3 can perform universal
computation only when combined with a concurrently running
initializer -- and so effectively be but part of a larger physical system.

The true universality of the 2-3 could still be shown, I suppose.
I think it is this:

  Hypothesis:
  Consider a 2-3 machine given the problem of simulating a 2-3
  machine plus the initializer of Smith's construction.  Every
  input problem to the simulated 2-3 machine can be simulated by
  giving the simulating 2-3 machine a tape initialized in a finite
  region with either constant or random semi-tapes beyond that.
  The a finite initialized region of the meta-encoding of the problem can
  be constructed from a finite encoding of input problem by an
  effective process that can be implemented by a machine in at least
  one of the lower three Chomsky-hierarchy classes of classical machines.

  If Smith's construction suggests, via the trick of meta-circular 
interpretation,
  a *finite* encoding for input problems to a 2-3 -- then (and only then)
  is the 2-3 itself universal.

That is, a universal machine is one that can, given nothing more than
the *complete* description of a computational problem, perform the
indicated computation.

The input to the 2-3 machine, as Smith's construction stands, is
never complete -- it relies on a concurrent external process to keep
expanding the description of the input problem.

The conditions of the hypothesis would clearly establish that
Smith has proved more than the (interesting) universality of a
machine that includes the 2-3 as a the sole unboundedly-strict
sub-component (if, indeed, that is what the construction of a
halting-detector shows).

-t