[drdeca]

Scott Aaronson has, iirc, suggested the idea that the complexity of such an isomorphism could be the distinguishing thing between whether or not something should be said to be computing a particular think. Sounds plausible to me.

[tsimionescu]

I believe that if you could prove that you have an actual isomorphism in the full formal sense of the world, the question about its complexity wouldn't really matter.

However, for a practical claim, it is probably impossible to formally prove that an interpreter function is both bijective between a physical system and a computation (it maps absolutely every possible state of the physical system to exactly one step of a computation).

However, it's important that the following argument can be made: if the evolution of a physical system is isomorphic to a computation of a particular algorithm for solving the traveling salesman problem, and if the phsyical system needs ~1 second for each step, then the system can't go from state A to state B in less than X seconds, where X is the number of steps required by that algorithm to reach those same steps. The actual interpretation of the algorithm or its purpose is not relevant here, the mathematical limits of how the computation happens remain relevant regardless.

That is because you can't find 2 different isomorphisms between the same physical system and 2 different computation that are not isomorphic to each other, if these are actual proper isomorhpisms (bijective) and not just hand-wavy analogies.

[happythomist]

Why should the complexity matter, so long as the computation is recognizable as such?

[AgentME]

It's possible create an interpretation where all of the computation happens in the interpreter instead of the system being interpreted.

With the right algorithm, could interpret the randomly moving particles in a gas as computing conway's game of life or anything else, if the algorithm just disregards everything about the particles and contains instructions that generate the expected results from conway's game of life. In that extreme case, I don't think it's useful at all to claim that the gas particles are simulating conway's game of life.

In an opposite extreme, you could say that the randomly moving particles in a gas are computing the motion of the random movements of particles in a gas. The interpretation algorithm is just "look at the particles at time t. Their locations represent the particles' locations at time t.". It's clear here that the system being interpreted is in fact doing all the computation and that nothing is hidden in the interpreter's work.

One interesting way to try to differentiate these two cases is that if you want the results of a longer-running simulation, then in the latter case, you let the actual system run longer, and the work to interpret it doesn't increase at all. In the former case, if you want to get the results of running conway's game of life for 2000 steps instead of 1000 steps, then it doesn't matter how long you let the gas particles go on for, but you do have to do more work on the interpreting side.