Re: [CL] Re: Decidability
Dear All,
I read with interest the discussion on the relevance
of decidability, but do not agree with the consensus that
seems to have been arrived at.
I have spent much time working with semi-decidable
and even fully undecidable languages; and from the
point of view of representing information and formulating
ontologies, I would say that decidability is not something
that should be sought at all cost. In fact it seems likely
that any language sufficient to represent anything like the
richness of human thought must be undecidable.
However for processing and computation, decidability is
undoubtedly of utmost importance -- much more important
than the lower complexity boundaries, I would say.
The main problem is of course that if I am really dealing with
a truly undecidable problem (such as computing entailment)
in some language), I cannot even write an algorithm to
do this.
If I have a semi-decidable language, the situation is very
slightly better because at least I have a test for positive
cases -- but it's not much better, because the complexity
of this test is not bounded by any function (so neither
time nor memory requirement are bounded).
Once I have a decidable problem/language I can worry about
specific complexity classes.
However, in many cases the complexity class does not directly
affect the practical scalability. This is because complexity
classes deal in worst cases. These typically arise quite rarely
compared to the average case. Thus it may well be that
a cubic algorithm works pretty well in almost all cases
(and hence could be perfectly acceptable to web users
who seem remarkably tolerant to systems that don't always
work).
Incidentally, I note that John chose Horn clause logic as a
good language. This is of course decidable (for 1st order
and I think also with modadic predicate variables) but, if
I remember correctly, exponential in complexity.
Thus the halting problem is solvable for "pure" Prolog
programs (but not if one uses the various messy stuff that
makes real programming possible).
So the clever Prolog programmer does not tame the
undecidable but rather steers around the exponential.
Best regards
Brandon
John F. Sowa wrote:
> Pat, Chris, Michael, et al.,
>
> I agree with Pat that decidability tells us only that
> a particular problem is solvable in a finite amount
> of time, but since it sets no limit on that amount,
> it is of much less value than giving us a better
> upper bound, such as exponential, polynomial, linear,
> or logarithmic.
>
> The attached diagram, complex.gif, illustrates the
> issues by showing a range of complexity classes as
> a function of the number N of items involved:
>
> 1. The upper bound is infinity for truly undecidable
> problems that cause the computer to loop forever.
> Knowing that a problem is decidable tells us only
> that it takes something less than infinity.
>
> 2. Exponential time is usually considered bad, but
> for small values of N (around 10 or less), it
> might not be bad. For N=100 or more, it is
> disastrous.
>
> 3. Polynomial time is often considered *tractable*
> or good, but for N of the size of the web (several
> billion pages and counting), N-squared time can
> be thousands or millions of years.
>
> 4. (N log N) is proportional to the time a good
> algorithm requires to sort N items. Algorithms
> of this complexity or less are *scalable* since
> they can be applied to the web and other large
> collections of data with current technology.
>
> 5. The ideal is constant-time algorithms, which are
> independent of the size of the data. Hash coding
> can come close to this limit, but the time to build
> the hash tables for N items tends to be (N log N).
>
> Bottom line: Complexity issues are very important, but
> decidability is an insignificant aspect of complexity
> when we are concerned with data of the size of the web.
>
> John
>
>
> ------------------------------------------------------------------------
>
--
===============================================================
Dr Brandon Bennett
Division of Artificial Intelligence Tel.: +44 (0)113 343 1070
School of Computing (room 9.16) (home) +44 (0)113 274 6920
University of Leeds Fax.: +44 (0)113 343 5468
Leeds LS2 9JT E-mail: brandon@comp.leeds.ac.uk
United Kingdom WWW: http://www.comp.leeds.ac.uk/brandon/
===============================================================