Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

With this example, a human can examine the implementation of the doesHalt function to determine what it will return for the input, and thus whether the program will halt.

Note: whatever algorithm is implemented in the doesHalt function will contain a bug for at least some inputs, since it's trying to generalize something that is non-algorithmic.

In principle no algorithm can be created to determine if an arbitrary program will halt, since whatever it is could be implemented in a function which the program calls (with itself as the input) and then does the opposite thing.



The flaw in your pseudo-mathematical argument has been pointed out to you repeatedly (maybe twice by me?). I should give up.




Consider applying for YC's Winter 2026 batch! Applications are open till Nov 10

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: