Tag: Undecidability

Gödel’s Proof and Einstein’s Dice: Undecidability in Mathematics and Physics – Part II

Posted on by Jochen Szangolies

by Jochen Szangolies

Commemorative plaque at Gödel’s former house in Vienna. Image credit: By Beckerhermann – Own work, CC BY-SA 4.0, via wikimedia commons

The previous column left us with the tantalizing possibility of connecting Gödelian undecidability to quantum mechanical indeterminacy. At this point, however, we need to step back a little.

Gödel’s result inhabits the rarefied realm of mathematical logic, with its crisply stated axioms and crystalline, immutable truths. It is not at all clear whether it should have any counterpart in the world of physics, where ultimately, experiment trumps pure reason.

However, there is a broad correspondence between physical and mathematical systems: in each case, we start with some information—the axioms or the initial state—apply a certain transformation—drawing inferences or evolving the system in time—and end up with new information—the theorem to be proved, or the system’s final state. An analogy to undecidability then would be an endpoint that can’t be reached—a theorem that can’t be proven, or a cat whose fate remains uncertain.

Perhaps this way of putting it looks familiar: there is another class of systems that obeys this general structure, and which were indeed the first point of contact of undecidability with the real world—namely, computers. A computer takes initial data (an input), performs a transformation (executes a program), and produces a result (the output). Moreover, computers are physical devices: concrete machines carrying out computations. And as it turns out, there exists questions about these devices that are undecidable. Read more »



Gödel’s Proof and Einstein’s Dice: Undecidability in Mathematics and Physics – Part I

Posted on by Jochen Szangolies

by Jochen Szangolies

God’s dice? Image by S L on Unsplash

TWA Flight 702 left New York at 7 AM on Monday, Feb. 4 1974, to arrive in London at 7 PM—some 40 minutes early. We know this thanks to the meticulous note-taking habits of visionary physicist John Archibald Wheeler, coiner of such colorful terms as ‘quantum foam’, ‘wormhole’, ‘superspace’ and ‘black hole’.

Wheeler spent the flight occupied with what he is perhaps best remembered for: pondering his ‘Really Big Questions’ (RBQs), among which we find perennial mysteries such as ‘How come existence?’ or ‘What makes meaning?’. The RBQ that occupied Wheeler on this particular day, however, was one that in many ways lay at the nexus of his thought: ‘Why the quantum?’

Wheeler had been a student of Bohr and Einstein, and thus, had learned about quantum mechanics straight from the horse’s mouth. Yet, he would struggle with the implications of the theory for the rest of his life, referring to the fundamental indefiniteness of its phenomena as the ‘great smoky dragon’. He was searching for a way to dispel the smoke, and in the note composed on Flight 702, draws a surprising connection to another remote frontier of human understanding—the phenomenon of mathematical undecidability, as discovered in 1931 by the then-25 year old logician Kurt Gödel. (The note itself is available online at the John Archibald Wheeler Archive curated by Baruch Garcia.)

At first sight, one might suppose this connection to be little more than a kind of ‘parsimony of mystery’: in substituting one riddle for another, the total number of unknowns is reduced. Indeed, the idea of ripping Gödel’s result from the austere domain of mathematical logic and injecting it into physical theory is controversial—earlier, during the writing of his magisterial textbook on General Relativity, Gravitation, with Charles Misner and Kip Thorne, Wheeler had confronted Gödel himself with the idea, who did not react too enthusiastically. Read more »