2 ms·
"Turing was wrong: the halting problem may be decidable after all! Selecting programs at random from the space of Turing-complete programs we show that almost a
by pmoriarty 8y ago
"Turing was wrong: the halting problem may be decidable after all! Selecting programs at random from the space of Turing-complete programs we show that almost all of them stop. Therefore, the answer of the Halting problem is "no", with probability 1."
Doesn't providing a single counterexample of a non-halting program prove them wrong?
- FartyMcFarter 8y agoYeah I suspect this is a tongue in cheek (but still silly) title. The halting problem is not about probabilities at all. If there's even one single program that cannot be proven to halt or not, that already makes the halting problem undecidable, regardless of the fact that an infinity of programs can be proven to halt / not halt.
- eugenhotaj 8y agoThis is equivalent to claiming that if you randomly sample from the real number line the probability of sampling a natural number is 0, therefore natural numbers can't exist. (Of course I doubt the author(s) were making these claims in all seriousness).