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