The Universal Universe, Part III: An Answer to Wigner

Eugene Wigner was a Hungarian American physicist and mathematician, who played a pivotal role in recognizing and cementing the role of symmetries in quantum physics. However, this is not the role in which we meet him today.
Rather, I want to talk about an essay he wrote, probably his most well-known and influential work outside of more technical physics publications. The essay bears the title The Unreasonable Effectiveness of Mathematics in the Natural Sciences [1], and it is a brilliant musing on the way we come to understand, model, and even predict the behaviour of physical systems using the language of mathematics, and the fundamental mystery that lies in the (apparently) singular appropriateness of that language.
Wigner's wonder is two-pronged: one, mathematics developed in one particular context often turns out to have applications in conceptually far removed areas -- he provides the example of π (or τ if you're hip), the ratio of a circle's circumference to its diameter, popping up in unexpected places, such as a statistical analysis of population trends, which seems to have little to do with circles; two, given that there is this odd 'popping up' of concepts originally alien to a certain context in the theory supposedly explaining that very context, how can we know that there is not some other, equally valid (i.e. equally powerful as an explanation) theory, making use of completely different concepts?

The Universal Universe, Part II: ...but is it?

I have ended the previous post with the encouraging observation that if the universe is computable, then it should be in principle possible for human minds to understand it -- the reasoning essentially being that each universal system can emulate any other. But the question now presents itself: is the universe actually computable?
At first sight, there does not seem any necessity for it to be -- after all, computation and computational universality may be nothing but human-derived concepts, without importance for the universe as it 'really is'. However, we know that it must be at least computationally universal, as universal systems can indeed be build (you're sitting in front of one right now) -- the universe can 'emulate' universal systems, and thus, must be universal itself (here, I am using the term universal in the somewhat loose sense of 'able to perform every calculation that can be performed by a universal Turing machine, if given access to unlimited resources'). Thus, the only possibility would be that the universe might be more than universal, i.e. that the notion of computation does not suffice to exhaust its phenomenology.
And indeed, it is probably the more widespread notion at present that the universe contains entities that do not fall within the realm of the computable. The discussion is sometimes framed (a little naively, in my opinion), as the FQXi did recently in its annual essay contest, in the form of the question: "Is reality digital or analog?"

The Universal Universe, Part I: Turing machines

In the mid-1930s, English mathematician Alan Turing concerned himself with the question: Can mathematical reasoning be subsumed by a mechanical process? In other words, is it possible to build a device which, if any human mathematician can carry out some computation, can carry out that computation as well?
To this end, he proposed the concept of the automated or a-machine, now known more widely as the Turing machine. A Turing machine is an abstract device consisting of an infinite tape partitioned into distinct cells, and a read/write head. On the tape, certain symbols may be stored, which the head may read, erase, or write. The last symbol read is called the scanned symbol; it determines (at least partially) the machine's behaviour. The tape can be moved back and forth through the machine.
It is at first not obvious that any interesting mathematics at all can be carried out by such a simplistic device. However, it can be shown that at least all mathematics that can be carried out using symbol manipulation can be carried out by a Turing machine. Here, by 'symbol manipulation' I mean roughly the following: a mathematical problem is presented as some string of symbols, like (a + b)². Now, one can invoke certain rules to act on these symbols, transform the string into a new one; it is important to realize that the meaning of the symbols does not play any role at all.
One rule, invoked by the superscript 2, might be that anything that is 'under' it can be rewritten as follows: x² = x·x, where the symbol '=' just means 'can be replaced by'; another rule says that anything within brackets is to be regarded as a single entity. This allows to rewrite the original string in the form (a + b)·(a + b), proving the identity (a + b)² = (a + b)·(a + b).
You can see where this goes: a new rule pertaining to products of brackets -- or, on the symbol level, to things written within '(' and ')', separated by '·' -- comes into effect, allowing a re-write to a·a + b·a + a·b + b·b, then rules saying that 'x·y = y·x', 'x + x = 2·x', and the first rule (x² = x·x) applied in reverse allow to rewrite to a² + 2·a·b + b², proving finally the identity (a + b)² = a² + 2·a·b + b², known far and wide as the first binomial formula.