entscheidungsproblem
fuck it, we're doing philosophy of math today
yeah, this is ostensibly a men’s style substack, but if I’m putting something out every day, I’m going to mix up the topics. and today, some hundreds of you are going to learn something you weren’t planning on learning. today, you’re going to learn how a bunch of weirdo mathematicians helped win World War II.
back about a hundred years ago, some philosophers and mathematicians were mulling over some stupid-sounding questions. questions like, is there a standard, generic procedure you can use to take a logical statement and answer “yes” if you can prove it’s true or answer “no” if it can’t be proven true. that probably doesn’t sound that hard or that interesting, huh? David Hilbert asked this question in 1928. the question was called “entscheidungsproblem,” or “decision problem,” in English.
well… about eight years later, this guy named Alonzo Church and his student, Alan, proved that… no, it can’t be done, there is no one procedure. in fact, they proved that you need an infinite number of new procedures, but one thing at a time…
the idea was… imagine a machine that can do this procedure, and answer whatever logical question you give it with a “yes” or a “no.” assume that machine exists. then, ask the machine, “if I ran procedure A on input B, would this machine come to an answer, or would it just run forever?” this question is called the Halting Problem; giving out an answer is “halting,” otherwise you run forever.
what if I asked this machine: “would procedure Z halt when you give it Z as input?” Then comes our next question, C. If Z halts on input Z, then C takes input Z and runs forever; if Z runs forever on input Z, C halts.
then let’s ask what happens when you input C into C. First, C asks whether C halts on C, and then, whatever it says, C does the opposite. … wait. that’s bad.
our magical first procedure, that machine that decides everything, is supposed to give us an answer, but C here creates a logical contradiction: if it halts, it doesn’t halt, and if it doesn’t halt, it halts. that can’t be. we assumed the machine exists, and then we used that to prove something that can’t possibly true. so there’s only one possibility remaining: the machine doesn’t exist.
you can’t have a machine that answers all these questions, because you can’t have a machine that answers the halting problem.
this is referred to as the “Church-Turing thesis.” their plan was just to answer this weird, abstract, philosophical question, but that idea—the machine—well, it turns out they accidentally stumbled onto something important.
Alan Turing devised a machine that couldn’t exist, but in so doing, he also devised a whole category of machines and procedures that could.
a “Turing Machine” technically cannot exist since part of its definition is infinite memory, but there are plenty of machines like it that can exist. we can talk about what is and is not computable. and we can put together a procedure for, say, breaking through the German Enigma machine.
the Enigma machine was the Nazis’ favorite device for encrypting messages. it was very clever at the time, and very hard to crack. until Turing came along and kicked its ass. this academic, hypothetical mathematician turned into… maybe the single greatest war hero in history? and also, the device you’re reading this on wouldn’t exist if not for him.
… then the British punished him for being gay and he killed himself.
also, “The Imitation Game” dramatizes his life by pretending that his homosexuality got him blackmailed during the war. blackmail has been used as a bullshit retroactive justification for laws against homosexuality, so this choice sucks. Breaking the Code is a better movie, watch that one instead.