That seems kind of bogus because you've just disguised an unsolved math problem as a computer program. It's like me making a program like this:
if fermats_last_theorem_holds(x,y,z):
halt()
else:
infinite_loop()
Will this program halt for all possible input integers > 2?
It may be able to "trick my brain" but only because I don't have a PhD in mathematics. Obviously no general algorithm can solve this, or else said general algorithm would easily be able to solve all unanswered questions in mathematics, physics, etc. Yet, human mathematicians are able to determine whether my program above halts, even if a general algorithm can't.
> 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.
umvi|6 years ago
It may be able to "trick my brain" but only because I don't have a PhD in mathematics. Obviously no general algorithm can solve this, or else said general algorithm would easily be able to solve all unanswered questions in mathematics, physics, etc. Yet, human mathematicians are able to determine whether my program above halts, even if a general algorithm can't.
Strilanc|6 years ago
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.