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

The great thing about undecidable problems is, that you can put an arbitrary amount of research in and you'll probably find another subclass of instances for which the problem is indeed decidable.

Only an infinite number of subclasses of instances to go.

That's proven job safety for computer science researchers.



> Only an infinite number of subclasses of instances to go.

There's only one subclass of instances for which the problem is undecidable: those where the program being analyzed is allowed to consume infinite memory.

Which is not the same thing as saying that the program is implemented in a Turing-complete language.

Because you can write a program in a Turing-complete language and yet, run it on a machine with finite memory (i.e. a computer).




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

Search: