Re: [CL] Re: Decidability
Chris,
I completely agree with your conclusion. If all the
logicians working on the Semantic Web would say that,
I would be happy:
> And I say again, I use decidable and undecidable
> reasoners all the time, and find them all useful.
> As with all these silly kinds of arguments, it boils
> down to having a good set of tools available, and
> knowing their characteristics. Decidability is
> one characteristic. It's useful to know. That's
> all. No big whoop.
What started this series of notes was that original
quotation I circulated, which was triggered by some
people who have been trying to make decidability
a nonnegotiable requirement for any version of
logic used on the Semantic Web.
I agree with you that it's important to know,
and to know when it's relevant or irrelevant
to a particular kind of problem.
However, I do want to clarify the relationship:
> What your diagram seems to imply is that decidability
> is somehow related to N, which it is not. An undecidable
> problem can manifest in a small data set. THAT is the
> problem and why it is useful to know.
Please note the two endpoints in the diagram, both of
which are independent of N: a constant-time algorithm
is finite and unchangeable for any N, and an undecidable
problem takes infinite time for any N.
I think that's a useful way to look at the relationship:
undecidability is the upper limit of the whole range
of complexity classes.
John
