The Limit of Computation
The Relationship Between Math and Truth
During the height of the second world war‚ British ships (slow moving steel giants) pushed through the endless blue Atlantic. Under them‚ hidden in the dark water waiting are German U-boats. They strike‚ sending torpedoes ripping through the sea. After an attack‚ those elegant British ships sink‚ becoming homes for thousands of sea creatures. But the battle for the Atlantic wasn’t fought only at sea. Hundreds of miles inland‚ at Bletchley Park in England‚ a man worked to prevent these attacks by cracking the Nazis’ cipher. The war demanded faster codebreaking‚ but Turing’s wartime methods were rooted in a deeper question he had explored years earlier—a question not about ships or torpedoes‚ but about mathematics.
The Impossible Recipe
The question Turing had grappled with was the “decision problem”: Is there a method or algorithm that can determine‚ for any mathematical statement‚ whether it’s true or false? To address this‚ Turing rigorously defined a machine capable of performing any “effective procedure” (logical processes that could be executed step by step). This is a computer‚ and since mathematical proofs are just such algorithms‚ they could be represented as programs. Rather than looking at math statements directly‚ Turing could instead ask whether there exists an algorithm that could be used to tell you if any other algorithm will halt or run forever on a given input. He proved such an algorithm is impossible.
I find this recipe analogy helpful in understanding his point conceptually. Imagine people growing frustrated with recipes that never end—ones that tell you to stir forever or to repeat steps 1–4 endlessly. Someone proposes a magical book where you can look up a recipe and it will tell you if that specific recipe is one that never ends. However‚ to prove that the magic book is a scam another person writes a recipe called Paradox: Step one‚ check what the magic book says about this recipe. If the book says it will finish‚ then never stop cooking. If the book says it won’t finish‚ then stop immediately. This paradox shows the magic book can’t work or exist. Turing did the same thing‚ only with algorithms proving the impossibility of determining for all mathematical statements‚ whether it’s true or false with a mathematical proof.
The Limits of Computation
Turing’s proof wasn't only about mathematics it tells us something about logic and human reasoning in general. He shows that even in abstract logic‚ there are unanswerable questions. We might imagine that intelligence‚ evidence‚ and reasoning all truth could be discovered. These proofs show that idea is incorrect. This suggests there are logical questions with definite answers that no algorithm can uncover. That challenges the assumption that truth and logical discoverability always align and forces us to ask: When I ask a question‚ what does it mean for the answer to be true? What is the relationship between truth and logic? It’s possible that truth is what can be derived computationally—that the universe follows a set of rules‚ like a unified theory of physics‚ and only what those rules can produce in a step-by-step method is true. But this view struggles with questions like Turing's “Does this program halt?”—which clearly has a true answer(yes or no)‚ even if no algorithm can find it. Perhaps truth includes everything that could be understood—though not logically derived—given infinite time. For instance‚ if a program runs forever‚ that fact could become evident over eternity. This wouldn't be a logical proof but still understood to be true. But this view faces problems too: the murkiness of infinities actual existence and the difficulty of formalizing the concept of “understanding.”
Is Logic the Foundation of Truth?
Perhaps the most compelling view is that logic comes from truth‚ not the other way around. In philosopher René Descartes' most famous work‚ “Meditations‚” he imagines an all-powerful demon deceiving him in every possible way. He concluded that all sense data could be false‚ even the laws of logic. But one truth remained undeniable: “I think‚ therefore I am.” A thought denying its own existence is still a thought. For Descartes‚ this kind of self-awareness came before logic. This idea can be extended to all sense experience. If you see a red apple‚ you can’t be sure the apple exists‚ but you can be certain you’re experiencing the sight of one without needing logical rules.
This was further developed by Immanuel Kant‚ who claimed that we never access things as they are—only as filtered through the mind. He believed logic was something the mind imposes to understand experience‚ not something that reveals the thing-in-itself (the noumenon)‚ which we can’t access directly. These views imply that truth and existence are prior to logic. But as subjective beings‚ logic is the only tool we have to access them. That means there can be truths that are unreachable by logic. “Logically provable‚” “understandable in infinite time‚” and similar concepts are just subsets of a greater‚ irreducible ground truth. But from our perspective‚ truth is grounded in logic—but that's not the end of the story.
Turing Return Home
After his life saving contribution to the defeat of the Nazi regime‚ Turing returned home. Sometime later‚ the authorities in Britain discovered he was gay. They stripped him of his security clearance and he was forced to undergo hormone therapy . The brilliant and curious man life was dimmed by shame and isolation‚ bearing the heaviness of emotional turmoil. In 1954‚ he took his own life. The facts of his genius and importance to our modern world are obvious and cannot be stated enough‚ but prejudice and judgment are of another kind. Here we move from logical truths to another kind entirely—emotional‚ moral‚ and ethical truths—those that live in human hearts and shape our most important choices. Some dismiss these as opinions because people can disagree or because they’re rooted in feelings‚ not logic.
Logic's Relationship to Emotions
But what are logical rules based on in the first place? Why must something be either true or false? Why does p=p feel necessarily true? These aren’t conclusions of logic—they’re rooted in shared intuitions. Modern neuroscience continues to find that emotion plays a role in all decision-making. Without emotional processing‚ people can't reason properly. Logic‚ then‚ may rest on feeling. The picture that this paints about human understanding and our relationship to truth is emotional not logical. There are truths about the world external to human minds. We access them through senses‚ experience‚ and feeling. Logic is simply the subset of truths undeniable to any rational agent—or required to build any system. Alan Turing's work did not only save lives in World War 2 but gives humanity a clearer understanding of our position in the universe.




I love that line about the magic recipes book it’s really cool 👌
I had never thought about certain equasions as recipes that never end. Great visual for us non-mathy types. Enjoyed this piece!