[Top] [All Lists]

[ontolog-forum] Theoretical issues and practical applications

To: "[ontolog-forum]" <ontolog-forum@xxxxxxxxxxxxxxxx>
From: "John F. Sowa" <sowa@xxxxxxxxxxx>
Date: Wed, 30 Dec 2009 11:06:10 -0500
Message-id: <4B3B7A72.1090301@xxxxxxxxxxx>
Chris and Len,    (01)

I'm happy to hear people discussing concrete issues that have
actually impinged on practical applications.  I changed the
subject line from the more cryptic "blogic iswc".    (02)

CP>> I assume it is a relatively un-contentious point that most
 >> business system building practitioners would be surprised to hear
 >> that (logical) intractability is anything other than a theoretical
 >> problem when building systems.    (03)

That is indeed true.  Every major programming language is capable of
expressing undecidable and intractable algorithms, and *nobody* is
asking for less expressive languages.    (04)

LY> ... but as a practitioner would like to add that even long periods
 > of not recognizing the term or the theoretical problem does not
 > always make it not a genuine category of problem.    (05)

That is also true.  Many practitioners have learned the hard way that
many of their projects have been failures.  However, the reasons for
their failures have ranged all over the lot:  poor human factors,
bad economics, poor choice of algorithms, incompetent implementers,
or just stupid ideas.  Theoretical issues have occasionally been
a cause of failure, but the causes are usually more mundane.    (06)

LY> But sooner or later engineering does come to a point where the
 > problem must be dealt with.  And when it does - the entire body
 > of practical acumen can become an obstacle to further progress.    (07)

I agree.  Practitioners rarely understand the theoretical issues,
and theoreticians rarely understand practical applications.  As a
result, we get knee-jerk slogans like "Expressive languages are
undecidable."  But that slogan is extremely misleading:    (08)

  1. Computational complexity is a property of *algorithms*,
     and *not* a property of problems or languages.    (09)

  2. Any given problem can be solved by many different kinds
     of algorithms of varying levels of complexity.    (010)

  3. Some problems, such as the traveling salesman problem, cannot
     be solved exactly by any tractable algorithm.  But many such
     problems can be solved to any desired degree of approximation
     by very efficient algorithms.    (011)

  4. Restricting the expressive power of a language *never* improves
     the efficiency of any computation.  The only thing it does is
     to make certain kinds of problems and algorithms impossible to
     express.    (012)

  5. Finally, *increasing* the expressive power of a language
     (e.g., by moving from integers to real numbers) can often
     allow intractable algorithms to be replaced by highly
     efficient algorithms.    (013)

We can't assume that every practitioner understands all these
fine points, and we can't assume that every theoretician will
understand the problems and issues of practical applications.    (014)

Therefore, we need a balanced collaboration of practitioners and
theoreticians to develop good paradigms and practices.  We need
a "cookbook" written by the chefs, so that novices have a guide
for preparing a decent meal.  In a hurry, we also need frozen
dinners that anyone can pop into the microwave.    (015)

John    (016)

Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/  
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/  
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/ 
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx    (017)

<Prev in Thread] Current Thread [Next in Thread>