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