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

I thought any general system contain arithmetic (as the proof based on transformation) cannot be proved it will be halted. Termination ... can it be terminated without halting?



Halting is indeed the same as termination. The halting problem DOES allow you to prove that some programs terminate. The problem is that there will be other programs that do terminate, but you won't be able to prove that they terminate.

So there is no way to know, for EVERY possible program, whether that program will terminate or not. But there are still some programs that you can know for certain that those programs will terminate.




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

Search: