I don't see what this paper is contributing other than the assertion that a physical system needs to functorially agree with the mathematical model that represents it. And that if that model is Turing complete, or represents some useful subset of computational functionality, then the physical system "computes." The fact that a sitting rock does nothing but sit is a perfectly fine, albeit severely limited, computational system (it even satisfies their definition of a computing physical system!). All of this just seems...obvious.
It looks like their definitions are so general that they don't answer their own questions, which by their main motivations (section XI) are fundamentally problems of construction and scale. It's not enough that there exists a theory that proves your physical system computes, you have to know the representation explicitly and be able to scale the system arbitrarily. [Edit:] The problem being that this doesn't show up in their actual definitions.
Maybe I'm reading it too shallowly, though. Can someone who's more well-versed in the background of this paper explain it better? It also doesn't help my confidence that they seem to completely ignore the rest of computer science (mentioning Turing machines only as an aside, and as part of a false assertion about (quantum) Turing machines being the only universal logical systems).
The fact that a sitting rock does nothing but sit is a perfectly fine, albeit severely limited, computational system (it even satisfies their definition of a computing physical system!).
It does not fit their definition because the whole point of the paper is that a physical system is not computing anything unless an entity is using the system to compute something by encoding the problem into the state of the system and later decoding the answer from the state of the system.
I'd like to compute the identity function. Let me denote by 1 the presence of a rock, and 0 the absence of a rock. I'll set up the problem (the input) by placing a rock appropriately, and after ten seconds, I'll check to see the if a rock is present. If so, the output is 1, otherwise it is 0.
This is a theory, a valid interpretation, highly reliable, scales well, and it commutes. Why isn't it a computation by their definition?
Now it is a computation because you are the computing entity that encoded a problem into the system and later decoded the answer. They paper essentially establishes the distinction of a system just evolving under the laws of physics and using this evolution to compute something by assigning an interpretation to the state of the system. I could use the same stone to compute something different, for example the boring trajectory of a stone placed on a surface in a gravitational field, but without specifying what you are computing the stone is not computing anything.
Hacker News doesn't attract a ton of theoretical computer scientists, but have you read Scott Aaronson's paper on the subject? http://www.scottaaronson.com/blog/?p=1438
I read Scott's writing a lot, and in my opinion he seems to have the right attitude about it. He's very comfortable in the definition of a computer, and is very interested in the potential for physical computers that defy the ([edit] strong) Church-Turing thesis by using crazy weirdness of physics. Quantum circuits so far only might be such a system, since we still don't know whether BPP = BQP.
So the question isn't whether soap bubbles can do certain computations, but rather whether soap bubbles can efficiently compute functions that are NP-complete in classical computing models.
I should have said the "strong" Church-Turing thesis, which is a statement about efficiency: anything that can be computed efficiently can be computed efficiently by a Turing machine. In other words, if quantum computers can solve problems in polynomial time that classical computers cannot, then the strong Church-Turing thesis is false. The normal Church-Turing thesis, which just says that anything which can be computed can be computed by a Turing machine, is still true when you consider quantum circuits: Turing machines can simulate quantum computers just fine if you are happy to wait a long time.
That being said, there could very well be models of computing (based on weird physical phenomena) that violate one or both versions of the Church-Turing thesis. Scott has expressed a few times that the possibility intrigues him, though I don't know whether he would bet his life's fortune on one outcome or the other :)
It looks like their definitions are so general that they don't answer their own questions, which by their main motivations (section XI) are fundamentally problems of construction and scale. It's not enough that there exists a theory that proves your physical system computes, you have to know the representation explicitly and be able to scale the system arbitrarily. [Edit:] The problem being that this doesn't show up in their actual definitions.
Maybe I'm reading it too shallowly, though. Can someone who's more well-versed in the background of this paper explain it better? It also doesn't help my confidence that they seem to completely ignore the rest of computer science (mentioning Turing machines only as an aside, and as part of a false assertion about (quantum) Turing machines being the only universal logical systems).