An Open Letter to Invisibilia

Jeremy Kun

42

Ashot Vardanian: I thought he was referring to Gödel’s first incompleteness theorem (i.e., it’s impossible to prove every true math/logic statement, so some things will always be undecidable, so relying on an unsolved conjecture might or might not be a bug). But the entscheidungsproblem (“decision problem”, the problem of whether or not it’s possible to write a computer program that determines if arbitrary logic claims such as “this program is bug-free” are true or false) seems more like it. Wikipedia’s entscheidungsproblem article says that Church and Turing each proved that a general solution is impossible, and the proof is known as the Church–Turing thesis. These articles explain a lot.