The black hole of computation: A surprising math discovery | Joel David Hamkins and Lex Fridman

Quick Overview

Joel David Hamkins and Lex Fridman discuss the surprising mathematical discovery that the Halting Problem, despite being undecidable in the worst case, possesses a "black hole" structure, meaning a computer procedure can correctly decide almost every instance of it asymptotically.

Key Points: The main lesson of computability theory is that one cannot gain a thorough understanding of a program's behavior just by looking at it; one must run it, a robustness confirmed by Rice's Theorem. Hamkins and Maznikov investigated if the Halting Problem has a "black hole," defined as a decision problem where difficulty is concentrated in a tiny region, making it easy almost everywhere else. They proved that the Halting Problem for standard Turing machines does have a black hole, meaning a procedure exists to decide almost every instance correctly, with the asymptotic density of solvable programs approaching 100%. One trivial reason for non-halting, which contributes to the solvable percentage, is programs lacking any instruction that transitions to the halt state, accounting for a proportion that limits to "1 over e^2, 13 and a half%." A gigantic 'stupid reason' found is that for most programs, the computation stops because the head falls off the tape during a random walk simulation before repeating a state, which is computable as non-halting. The proof relies on the Polya Recurrence Theorem applied to the random walk behavior of the Turing machine head, showing it is very likely to return to the start, causing it to fall off the tape. This result extends to NP-complete problems, where feasible algorithms can often be proven to solve almost every instance of problems like the knapsack problem in a feasible amount of time.

Context: The discussion between Joel David Hamkins and Lex Fridman centers on computability theory, specifically the limits of determining whether an arbitrary program will halt (the Halting Problem). They explore the concept of a 'decision problem with a black hole,' a concept posed by Alexi Maznikov, which describes a problem that is almost entirely easy to solve, despite being undecidable in the worst case, making it unsuitable for use in critical applications like encryption.