Help: When are two computations isomorphic?
Lets work within the Turing machine model of computation and consider halting TMs. Given TMs named T and T’, when would you say they implement the same computation? I see at least two possibilities:
1) Call them equivalent if they have the same global output (i.e. T(x) = T’(x) for all x).
2) Call them equivalent if they locally transform the same way (i.e. their transition functions are equivalent in some sense).
In other words, is the step-by-step operation of the TM central to your notion of computation?
I came to this question when reflecting on a discussion here involving levels of simulation. I’m interested in thinking more rigorously about computations we care about in a dovetailing ensemble, and determining where in the hierarchy they are likely to lie.
(Note that the latter equivalence implies the former, and is thus stronger.)
There are a variety of different ways of regarding computations as somehow the same. For Turing machines the most basic form is to regard them as the same if they recognize the same languages (that is halt on the same inputs, accept the same inputs and reject the same inputs). This is probably too broad a definition for your purposes and doesn’t fit most of our intuitions. Thus, for example, two algorithms for determining if an integer is prime, one that uses brute-force, and one that does something quick and clever (e.g. Agrawal’s polynomial time algorithm) should probably not be equivalent for most purposes.
I’m not aware of a better definition that captures precisely what you want.
The notion of abstract state machines may be useful for a formalization of operational equivalence of computations.
Before discussing the specific question, I think it is worth attending to whpearson’s distinction between algorithms and fetch-execute cycles. A traditional Turing machine implements an algorithm beginning with an initial condition and proceeding to a final condition; the more general interaction machines can accept inputs during their operation which cause branching effects.
“The same computation” implies to me that the steps matter. What’s computed (the input->output mapping) may be the same, but how it’s computed may differ. I’d at least care about resources (time and space) used in the usual asymptotic way.
If one thinks of T and T’ as static set-theoretic objects (i.e. ugly 7-tuples) then the first perspective resembles calling two such objects equivalent if their boundary conditions are the same. The second strikes me as a more reasonable concept of isomorphism here. (This is essentially thinking about the question in the framework of Tegmark’s MUH).
I thought about this some more and the first perspective seems somewhat natural as well.
Consider the MUH’s cousin, the CUH (i.e. all computable mathematical objects are real). Each object can be thought of as an equivalence class (using the first equivalence I mentioned) of the TMs that compute it. If you have a strong belief in the CUH then the first equivalence seems to cut reality at its joints.
On a side note, it’s interesting that TMs are used to define computable mathematical objects and are also computable mathematical objects themselves. Following this train of thought might lead one to new notions of symmetry in this space of objects.