News for hackers. Stuff that matters.

A comment on A number that can't be calculated. Parent comment

Re:A number that can't be calculated by kotlin2 on Tuesday October 25, 2022 @04:10PM (#33335519)
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.
[ Parent | on HN ]
Re:A number that can't be calculated by alexmolas on Tuesday October 25, 2022 @04:35PM (#33335791)
no, 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/

[ Parent | on HN ]
Re:A number that can't be calculated by kotlin2 on Tuesday October 25, 2022 @04:50PM (#33335990)
Exactly. 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.

[ Parent | on HN ]