3 ms·
Yes, but that doesn't mean you can't describe it. The halting problem is undecidable, but it's really easy to describe the set of programs that halt. I just de
by mikeash 11y ago
Yes, but that doesn't mean you can't describe it.
The halting problem is undecidable, but it's really easy to describe the set of programs that halt. I just described it right there!
That quote is talking about defining the set, not determining whether a program is a member of the set (which is indeed impossible in the general case).