4 ms·
If 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 gen
by kotlin2 4y ago
If 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.