Orchid XP v8 wrote:
> ...so it's "undecidable" because you can't always figure out the answer
> in finite time?
Basically.
A (yes/no) problem is decidable if it's possible to write a program
which will eventually answer the problem for any given input. Your
algorithm will only answer "yes" (ie there is a root), but will fail to
ever give a "no" answer.
It's the same with the halting problem. It's trivial to write a program
which will tell if if another program eventually halts, but impossible
to always determine when it won't.
Post a reply to this message
|