Digital physics and "Gandy-like" machines Various physicists, famously John Wheeler, have asserted that physical information is the central object of study in physics, in the sense that an object or concept is "physically meaningful" if it makes a difference to the information that can be extracted from (actual or hypothetical) physical experiments. For example, gauge transformations are "unphysical" in this sense.
Some have gone further and proposed that the Universe is "computational in essence": that, at the most fundamental level, it consists of the processing of information according to fixed rules; see e.g. the Stanford Encyclopedia of Philosophy's article "Computation in Physical Systems" and Wikipedia's article on digital physics.
I am trying to understand the possible interpretation and coherence of this proposal.

Robin Gandy, in "Church's Thesis and principles for mechanisms", formulated a broad model for parallel computation subject to "locality" constraints. The model subsumes Turing machines and cellular automata, and is given in terms of hereditarily finite sets, although John Byrnes and Wilfried Sieg have recast it in terms of locally finite labelled graphs, in "A graphical presentation of Gandy's parallel machines".
Since the information processing in a Gandy machine is local, it seems plausible to me that this formulation is already consistent with relativity; if not, I can't imagine it being difficult to modify the definitions to make them so.
The "pancomputationalist" proposal might then be formalized as claiming that the Universe is (equivalent to) a "Gandy-like" machine. My question is: Is it possible for this proposal to be consistent with current physical observations? More precisely, are there any known obstacles to the possibility that some Gandy-like machine, with certain initial conditions, could exhibit "large-scale" behaviour consistent with current physical models? I am aware of several possible objections:


*

*The Church-Turing thesis may be false, in that there could be physical systems ("hypercomputers") capable of performing computational supertasks. An example is given by Oron Shagrir and Itamar Pitowsky in "Physical Hypercomputation and the Church-Turing Thesis". Whether such a device is physically possible is obviously unknown, but if so it would refute the proposal.

*Bell's theorem essentially* rules out local hidden variables, so the proposed "locality" of computation may not correspond simply to locality in spacetime (*another possibility is to reject counterfactual definiteness; this position is known as superdeterminism).

*Even the state of a simple quantum mechanical system resides in a Hilbert space and so contains an infinite amount of classical information. That said, the amount of information which may actually be extracted from a system (and is hence "physically meaningful") is finite. In particular, there is a bound due to Jacob Bekenstein which arises when considering thermodynamics together with general relativity. It states that the entropy (or, to my understanding, "classical information") enclosed in a region of space is bounded from above by the surface area of the region.
I have tagged this question as soft since it may not have a definite answer; nevertheless I would find relevant literature and discussion very useful.
Some may contend that this question belongs on physics.stackexchange rather than here; however, my perspective is that the question - at least, the more precise version of it stated above - is ultimately a mathematical one.
 A: This line of thought seems to be the essence of the research program of Gerard 't Hooft, as exposed in a series of papers culminating in the monograph The Cellular Automaton Interpretation of Quantum Mechanics.

A cellular automaton is a system with localised, classical, discrete
  degrees of freedom, typically arranged in a lattice, which obey
  evolution equations. The evolution law for the data in every cell only
  depends on the data in the adjacent cells, and not on what happens at
  larger distances. This is a desirable form of locality, which indeed
  ensures that information cannot spread faster than the speed of light.
  The Cellular Automaton Theory assumes that, once a universal
  Schrödinger equation has been identified that encapsulates all
  conceivable phenomena in the universe (a Grand Unified Theory, or a
  Theory for Everything), it will feature an ontological basis that maps
  the system into a classical automaton.
The Cellular Automaton Interpretation of quantum mechanics suggests to
  us what it is that we actually do when we solve a Schrödinger
  equation. We thought that we are following an infinite set of
  different worlds, each with some given amplitude, and the final events
  that we deduce from our calculations depend on what happens in all
  these worlds. This is an illusion. There is no infinity of different
  worlds, there is just one, but we are using the “wrong” basis to
  describe it, because the basis we are using is not an ontological one.

So, at least according to 't Hooft, the answer to the question of the OP "Is it possible for [a local cellular automaton] to be consistent with current physical observations?" is Yes.
