3 ms·
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
by tshaddox 4y ago
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.
- kevinventullo 4y agoIsn’t the crux of the issue that you can’t “observe” an infinite loop?
- morelisp 4y agoNo, the crux of the issue is that you can't observe every infinite loop.
- alexmolas 4y agoBut 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.