Hacker News new | past | comments | ask | show | jobs | submit login

Th original P is defined as a program that can decide whether any program halts or not. If your proposed P doesn't terminate for some programs, then it hasn't made a decision, and it's not really the P you set out to find.

In other words: can you make a P that decides correctly for -some- programs, but never gives an answer for others? Sure. (E.g., if the program is "while(true) {}", then it loops, otherwise I don't know.) But unless P works (terminates and gives a decision) for any arbitrary program, it's not generally useful.




Good point. But that doesn't mean it's useless. Check it with an external P: If it's a paradoxical process like is given in the proof, it won't finish, which will be detected, uniquely, as a paradox because it won't halt.


For what finite number of steps can we watch the program and know afterwards that it will never halt in the future?




Consider applying for YC's Spring batch! Applications are open till Feb 11.

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

Search: