4 ms·
The Halting Problem forbids you to build an algorithm that proves if a generic problem halts or not. This doesn't forbid you to check if a specific algorithm ha
by alexmolas 4y ago
The Halting Problem forbids you to build an algorithm that proves if a generic problem halts or not. This doesn't forbid you to check if a specific algorithm halts or not. For example, you know that the specific program `print("Hello World")` halts. So you can remove the ones that do not halt by inspecting them one by one and developing a specific algorithm for each one that determines if it halts or not.
- kotlin2 4y agoIf you could inspect any Turing machine and devise a specific algorithm that determines if it halts, then you yourself would be an algorithm that solves the generic halting problem.
- alexmolas 4y agono, because you can build an algorithm that fools the algorithm that solves the generic halting problem. I wrote a "proof" of that in my blog [1] [1]: https://www.amolas.dev/blog/halting-problem/ https://www.amolas.dev/blog/halting-problem/
- kotlin2 4y agoExactly. So your claim that: > So you can remove the ones that do not halt by inspecting them one by one and developing a specific algorithm for each one that determines if it halts or not. Is impossible. You can’t, in general, inspect Turing machines one-by-one to determine if they halt.