TIM ROUGHGARDEN treats computation as a law of nature, tracing its arc from Turing's proof that some problems are unsolvable to the P versus NP question at the heart of modern computer science.
The halting problem, which asks whether a program will eventually stop running, is forever beyond the reach of any computer.
Or any human.
People have fumbled that recently: the halting problem isn’t just incomputable, it’s a paradox. It turns ‘anything is computable’ into a contradiction. It has no solution. When someone brings it up to dismiss the possibility of AGI, tell them to fuck off.
Computation is as real as math.
Or any human.
People have fumbled that recently: the halting problem isn’t just incomputable, it’s a paradox. It turns ‘anything is computable’ into a contradiction. It has no solution. When someone brings it up to dismiss the possibility of AGI, tell them to fuck off.