Hi Luca,
here`s a first quick reaction to your post.
Your first question is, essentially: how could one disprove the computational universe conjecture? Very important question indeed, in light of the fact that any serious physical theory should be such as to be possibly disproved.
So far, this conjecture (recently termed `Bit Bang`) rests upon the wide experimental evidence that many simple models of computation (not only cellular automata) lead to the emergence of very complex, nature-like patterns (including particle-like, self-reproducing and pseudo-random phenomena). A second crucial argument is the typing-monkeys scenario: in essence, the output of the monkey activity is in itself a random universe (of character strings) totally unlike ours, but when interpreted as a program, and run in a universal Turing machine, the distribution of the output strings (Levin`s `miracolous` distribution) is much more aligned with that mix of order and disorder that we see around us: order, in a computational universe, becomes not only possible, but even necessary. Lloyd (and, I believe, others too) suggest that this random-like input could be represented by the quantum fluctuations of the vacuum from which the Big (Bit) Bang originated. I guess these arguments nicely interplay with yours, when you deal with the puzzle of the simultaneous growth of structure and entropy in our universe.
Ok, but how about a potential falsification? The computational universe conjecture almost by definition rests a lot on computer simulations. In particular, one tries to see whether the `particles` that might emerge from animating a Plank-scale discretized spacetime - e.g. a causal set, or directed acyclic graph - can eventually reproduce, by an upward cascade of emergent layers, some known, observable phenomena, and associated measures (e.g. mass), as detected at the scales within reach of current instrumentation. If you come up with an algorithm that sets up a spectacular architecture of emergence, with all sorts of interacting patterns, but, when reaching the scales of subatomic particles, does not reproduce the elements of the standard model, than you have disproved your `theory`, which would then turn into a nice piece of recreational mathematics, like Conway Game of Life. Admittedly, a long and winding road.
I completely agree with you that the uniqueness of each human being, and its ability to act spontaneously, makes her unsuitable for treatment as a physical object - and puts her out of the reach of traditional physics (this is a key point in de Chardin`s `The Human Phenomenon`). There is a nice quote (from Schroedinger, I think, but I could not find it back) where living things are described as ones that keep moving also when, according to physical law, they should come to rest. One of the crucial and fascinating questions related, in particular, to computational theories of the evolving cosmos based on emergence, is to spot the moment, the emergent level when this (apparent?) ability to act spontaneously appears. Following de Chardin, I believe that this agency skill should appear very soon, much before the appearance of life as traditionally conceived.
I do have the time for reading and commenting your essay, and I`ll do it very soon.
Best regards
Tommaso