Human Ingenuity vs. the Computer’s Halting Problem
In a dialogue with a friendly skeptic, I suggested an explanation he found astounding but it’s the only possible oneWhen studying computer science a student invariably learns about the infamous halting problem. The problem states there is no general algorithm that can determine for every deterministic computer program whether that program will halt or not. This struck me as absurd when I first learned of the problem. Surely a whizkid like myself could design a simple algorithm to track the program’s memory and catch when it started repeating itself and determined it would not halt. Once convinced the problem was indeed provably unsolvable, I then thought the problem must show that humans are not computers. This is because it seems intuitive that for every program, if I watch it enough and think about it carefully enough, I should be…
