News for hackers. Stuff that matters.
Re:Landmark computer science proof cascades through physics ... by Strilanc on Thursday March 05, 2020 @02:57PM (#22497481)
> you've just disguised an unsolved math problem as a computer program

But that's the point! The halting problem hides inside of it all of the complexity of math, including the dark tricky self-referential corners. Saying that you can solve the halting problem is tantamount to saying you've solved Godel incompleteness.

If you applied the halting proof diagonalization step to yourself (modeled as a machine built of out physics) you would find that it spit out something very complicated that ultimately amounted to a program equivalent of a statement of the form "The physics machine that I am cannot prove this statement". If you proved the statement then that would disprove it, which is the core of the problem.

There are no comments on this comment yet.