CAN ALGORITHMS BE DECLARED "EQUIVALENT" ?
------------------------------------------
written by Andrew Clausen, from discussions with Peter Eckersley and Toby Ord

Consider an implementation of QuickSort in C, and another in Haskell.  Us
humans are probably pretty good at saying "these two programs work the same
way".  But, we don't have any mathematical tools for justifying such claims.
We would like to consider how we could determine if two programs use the same
algorithm.

Note: it certainly isn't possible to write a program to decide this (by Rice's
Theorem).  Furthermore, on the face of it, algorithmic equivalence is
subjective.  We're interested to see if there are any mathematical measures we
can apply that somehow match up to different intuitions.

As computer scientists, we love Turing machines!  However, Turing machines
can't do constant-time random memory access, so we will consider Register
machines instead.  All programs can be transformed into a Register machine.
However, it isn't clear if they will be "the same" after the transformation.
So, we will need to revisit this issue.

So, for two register machines to be "equivalent", they certainly need to give
the same outputs (or at least "equivalent outputs") when fed the same inputs.
They should also have the same asymptotic running time.  But what else?

We think it might be helpful to consider a pair of transformation register
machines "AB" and "BA" that somehow transform the running state of A to B and
B to A respectively.  If AB and BA run in O(n) time (for a yet-to-be-defined
n), then we might be able to say that A and B are O(n)-equivalent.

More formally:

DEFINITION:
Let A, B be two register machines.
Let I be the input, and O the output.  We will write O = A(I).
Let T(A, I) be the total running time of A on input I.
Let S(A, I, t) be the state of register machine A at time t on input I.

We will say that a register machine AB that can transform any state S(A, I, t1)
to some state S(B, I, t2) is an "A-B transformer".

Then, A and B are O(f(n))-equivalent if:
 * there exists an A-B transformer that runs in O(f(t1)) time, where t1 is
the timestep at which the state S(A, I, t1) is selected as input.
 * similarly, there is a B-A transformer that runs in O(f(t2)) time, where
t is the timestep of S(B, I, t2).
 * there exists t1' >= t1 such that:
 
	BA(AB(S(A, I, t1))) = S(A, I, t1')


DISCUSSION

The first thing to check: if A and B are identical (have the same
states, transitions, etc.), then are A and B O(1)-equivalent?
Answer: yes, since their states are the same at each time step, the
"do-nothing" algorithm.

The next observation is that any two sorting algorithms are
O(n log n)-equivalent, since AB could simply transform directly to the final
state in O(n log n) time.  Hopefully O(n) equivalence is more meaningful :)