Re:A number that can't be calculated
by tshaddox on Tuesday October 25, 2022 @03:40PM
(#33335189)
No, because the halting problem requires implementing a function that can compute whether any other function halts. It has to work for any possible function you give it. You can, of course, compute whether some functions halt. Two easy ways to do so are to observe that it halts or observe an infinite loop.
[ Parent
| on HN ]
Re:A number that can't be calculated
by kevinventullo on Tuesday October 25, 2022 @03:46PM
(#33335256)
Isn’t the crux of the issue that you can’t “observe” an infinite loop?
No, the crux of the issue is that you can't observe every infinite loop.
But if you know BB(n) for any n then you can just make run a program of length n for BB(n) steps. If after BB(n) steps it hasn't halted you know that the program will loop forever. Since you can do that for any arbitrary program then you could solve the halting problem.