Untangling Entanglement

What to Feynman was interference (see the previous post), to Erwin Schrödinger (he of the cat) was the phenomenon known as entanglement: the 'essence' of quantum mechanics. Entanglement is often portrayed as one of the most outlandish features of quantum mechanics: the seemingly preposterous notion that the outcome of a measurement conducted over here can instantaneously influence the outcome of a measurement carried out way over there.
Indeed, Albert Einstein himself was so taken aback by this consequence of quantum mechanics (a theory which, after all, he helped to create), that he derided it as 'spooky' action at a distance, and never fully accepted it in his lifetime.
However, viewing quantum mechanics as a simple generalization of probability theory, which we adopt in order to deal with complementary propositions that arise when not all possible properties of a system are simultaneously decidable, quantum entanglement may be unmasked as not really that strange after all, but in fact a natural consequence of the limited information content of quantum systems. In brief, quantum entanglement does not qualitatively differ from classical correlation; however, the amount of information carried by the correlation exceeds the bounds imposed by classical probability theory.

The Origin of the Quantum, Part II: Incomplete Evidence

In the previous post, we have had a first look at the connections between incompleteness, or logical independence -- roughly, the fact that for any mathematical system, there exist propositions that that system can neither prove false nor true -- and quantumness. In particular, we saw how quantum mechanics emerges if we consider a quantum system as a system only able to answer finitely many questions about its own state; i.e., as a system that contains a finite amount of information. The state of such a system can be mapped to a special, random number, an Ω-number or halting probability, which has the property that any formal system can only derive finitely many bits of its binary expansion; this is a statement of incompleteness, known as Chaitin's incompleteness theorem, equivalent to the more familiar Gödelian version.
In this post, we will exhibit this analogy between incompleteness and quantumness in a more concrete way, explicitly showcasing two remarkable results connecting both notions.
The first example is taken from the paper 'Logical Independence and Quantum Randomness' by Tomasz Paterek et al. Discussing the results obtained therein will comprise the greater part of this post.
The second example can be found in the paper 'Measurement-Based Quantum Computation and Undecidable Logic' by M. Van den Nest and H. J. Briegel; the paper is very interesting and deep, but unfortunately, somewhat more abstract, so I will content myself with just presenting the result, without attempting to explain it very much in-depth.