Mutual information is defined for two random variables, and random variables are mappings from a common sample space to the variables' domains. What are the mappings for two "things"? Mutual information doesn't just "exist", it is given by mappings which have to be somehow specified, and which can in general be specified to yield an arbitrary result.

I wasn't as precise as I should have been. By "mutual information", I mean "mutual information conditional on yourself". (Normally, "yourself" is part of the background knowledge predicating any probability and not explicitly represented.) So, as per the rest of my comment, the kind of mutual information I meant is well defined here: Physical process R implements computation C if and to the extent that, given yourself, learning R tells you something about C.

Yes, this has the counterintuitive result that the existence of a computation in a process is observer-dependent (not unlike every other physical law).

When you distinguish between the mappings "originating" in the interpreter versus in the "physical process itself", you are judging the relevance of output of mutual information calculation in the same motion ("no true Scotsman"). Mutual information doesn't compute your answer, deciding whether the mapping came from an approved source does.

No, mutual information is still the deciding factor. As per my above remark, if the source of the computation is really you, by means your ever-more-complex, carefully-designed mapping, then

P(C|self) = P(C|self,R)

i.e., learning about the physical process R didn't change your beliefs about C. So, conditioning on yourself, there is no mutual information between C and R.

If you are the real source of the computation, that's one reason the equality above can hold, but not the only reason.