“Emergence is strong with this one” — the free will loophole, part 2.
Alright, I am grateful that several people have pointed out to the weakest link of the argumentation in my previous post addressing Sabine Hossenfelder’s “How to live without free will”. Unsurprisingly, it’s the (admittedly quite strong) claim that computation theory is not weakly emergent from physics.
So here I will try to consolidate this claim. Don’t expect a full formal proof, I’m not math-savvy enough for that and it’s a vast topic for a blog post.
Let’s start with defining the problem more precisely. We are given a system of physical “small stuff” (particles) of which we know:
1. the complete physical description of the system’s “small stuff” down to arbitrary precision. This is a woefully unrealistic assumption for even relatively simple systems, but we’re investigating the situation “in principle”.
2. that it can perform some sort of “physical computation”, more precisely: given the initial state, part of which we can interpret as encoding some abstract “input”, the sytems evolves in time according to the laws of physics and some time later we can again measure a partial state of the system which we can interpret as output.
Hopefully most people will agree that the above is necessary and sufficient to link physics to computation in the sense we typically understand it. The initial state encodes both the input (if there is one) and the “program” executed by the computing. If you need an intuition, that is exactly what your modern silicon-based computer does. The program is encoded in the computer’s 0/1 circuits and then the physical machinery does the rest: a clock is triggering the step-by-step execution of the program by flipping bits.
It is, I think, this kind of intuition that make people question my strong emergence claim. After all, all physically realizable computations are implemented based on (quite simple) physics: essentialy, the ability to store and flip bits (or qbits). The computation, so the argument goes, is weakly emergent from just that: all properties of the system, no matter how complex, are predictable from its “small stuff”.
I will attempt to provide a couple of arguments that this picture of physical computation is superficial and misleading once sufficiently complex systems enter the picture. They all rely, in principle, on the fact that once physical system are performing arbitrarily complex computations, computational theory is no longer an abstract theory about algorithms, but it becomes a theory that makes predictions about the evolution of physical systems (at a level that is higher, ore more abstract, than the “small stuff”)
Argument 1: Computability and the halting problem. As stated in [1], computation can cause “that even if a system is deterministic it can be the case that we can’t predict its behavior in the long run”. It has been recently shown that, for certain classes of sufficiently complex physical systems, predicting certain observable properties (spectral gap) is equivalent to the halting problem. In other words, a certain observable property of a system is not merely hard to compute from their physical state, but “there cannot exist an algorithm or a computable criterion that solves the spectral gap problem in general” [3]. This result might seem at first somewhat weakened by the fact that, as common to halting problem results, it applies to infinite families of systems. However, the result implies that, when analyzing an individual finite system “there are particular cases within these families for which one can neither prove nor disprove the presence of a gap, or of any other undecidable property” [3].
In itself, this does not yet endorse computation as not being weakly emergent, because it basically states that nothing, including any kind of computation, can be used to predict the evolution of the system. Please read on.
Argument 2: “insider knowledge” — I have been trying to put this together more formally, but I’m only partially succeeding. Proofs are hard.
Let’s consider a finite system S1 of “small stuff” performing a particular computation. Say, one that is known to be computationally irreducible, which means that the computation itself is the fastest process that predicts the evolution of the system — or, conversely, no other computation predicting the system’s output can be faster [1, 5]. As you can see in the figure, S1 can be actualy part of a (much) larger physical system.
This setup already leads to a somewhat strange situation:
(1) if we know a priori which part of S1 is encoding the procedure/state and which one the input (the “meaning” of the colored dots), then we can predict the output in the guaranteed fastest way as per the computational ireducibility we’ve chosen for our algorithm.
(2) if we don’t have that insight, all we see is a bunch of “small stuff” doing something arranged in a particular configuration we know perfectly. Everything is black dots, apart for the blue dots (we know which parts to observe as output otherwise “computation” does not make any sense) but, crucially, we don’t know which “small stuff” is encoding the input, which “small stuff” is encoding the computation states and which “small stuff” is completely unrelated. Predicting the output of the system would thus mean either (a) simulating the whole system or (b) attempting to reverse-engineer the computation algorithm. Both options are equivalent to the halting problem: the first as per Argument 1 and the second because the reverse-engineering procedure is essentially theorem proving (known to be equivalent to the halting problem).
It follows therefore that “insider knowledge” — knowledge about a computation-theoretical aspect of the system that is not part of its physical description — allows a type of computation that cannot be deduced from physical description alone. Therefore, computation cannot be weakly emergent from the “small stuff”.
Argument 3: partial invariance. If computation was weakly reducible to particle physics, then one would expect it to change radically when changing the underlying physical theory. But when switching from classical to quantum physics, computational theory is partially invariant to this change. For instance, nothing changes about some fundamental results such as the halting problem (no uncomputable functions suddenly become computable — quantum computing is Turing-equivalent to its classical counterpart) or the P=NP question: most “hard” problems remain hard in quantum computing. Which suggests that computation as a theory has some features that are independent of the basic physics .
Argument 4: computational complexity. An essential part of the argument against strong emergence is that the behavior of bigger stuff is computable in principle from he behavior of small stuff. Here, “in principle” is used to dismiss computational efficiency as only a practical matter.
But the very laws of physics impose a limit to whatever can be stored and computed in a finite region of space — the Bekenstein limit [2]. It seems therefore that computing the behavior of extremely complex systems as per Argument 2 setup might not be merely “impractical”, but physically not realizable due to the Bekenstein limit: the attempt to simulate the system in a way that is, say, exponentially less efficient will either run out of the “small stuff” in the visible Universe or collapse into a black hole (see [2] for details).
There, I’ve done it: I wrote 4 arguments pro-strong emergence of computation. Sincerely looking forward to people demolishing them as well as maybe impoving them with stuff I don’t know (of which there is plenty out there in the computable Universe).
References:
[1] https://www.researchgate.net/publication/51956550_Emergence_Complexity_and_Computation
[2] https://www.scottaaronson.com/blog/?p=3327
[3] https://arxiv.org/pdf/1502.04135.pdf
[4] http://www.consc.net/papers/emergence.pdf
[5] Wolfram S.,Statistical Mechanics of Cellular Automata,Rev. Mod. Phys. 55, 601–644, 1983