May 28, 2025What does "Undecidable" mean, anywayAn explainer for people who don't know computer science and are mildly curiousSystems DistributedI'll be speaking at Systems Distributed next month! What does "Undecidable" mean, anywayLast week I read Against Curry-Howard Mysticism, which is a solid article I recommend reading. For example, I can reframe the function add(x, y) = x + y as a decision problem like this:IS_SUM(str) { x, y, z = split(str, "#") return x + y == z }Then because IS_SUM("2#3#5") returns true, we know 2 + 3 == 5 , while IS_SUM("2#3#6") is false. (total) Turing MachinesA Turing Machine (TM) is a particular type of computation model. It's possible to write a Turing machine that takes a textual representation of another Turing machine as input, and then simulates that Turing machine as part of its computations.