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

> We programmers write halting programs with great regularity.

Making any program halting program is trivial: add executed instructions counter, halt program at some value of the counter. Proving that an arbitrary program halts is an entirely different task.

> So, the fact that we cannot solve some problems does not imply we are not halting oracles.

If it's allowed to not solve some problems, then I can write such an oracle:

Run a program for a million steps. If program has halted, output "Halts", otherwise output "Don't know".

It can't solve some problems, but by your logic it doesn't imply it's not a halting oracle. You are missing something.



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

Search: