[Top] [All Lists]

Re: [ontolog-forum] (Resending) Nonmonotonic Reasoning

To: ontolog-forum@xxxxxxxxxxxxxxxx
From: "John F. Sowa" <sowa@xxxxxxxxxxx>
Date: Sun, 25 Mar 2012 23:18:14 -0500
Message-id: <4F6FEE06.80402@xxxxxxxxxxx>
On 3/24/2012 2:35 PM, Simon Spero wrote:
> In the case of Prolog, we're never in P to begin with...    (01)

That is certainly true.  And that is one is one of its
greatest strengths.    (02)

> With prolog, the biggest problem is that, by requiring all
> possible proof trees to be explored, any infinite search trees
> that might not be explored in a successful positive query will
> lead to non-termination in what should be a successful negative
> query.    (03)

Yes.  That is why you should never let naive users make design decisions
about what languages and algorithms to use to solve their problems.    (04)

Some points:    (05)

  1. Computational complexity is first and foremost a property
     of *problems* -- and only indirectly and *misleadingly*
     a property of languages.    (06)

  2. Restricting the expressive power of a language *cannot* improve
     its efficiency on any problem.  It merely makes some problems
     impossible to express.    (07)

  3. All useful programming languages are Turing complete, but they
     can be used very efficiently for a huge number of problems.
     They solve polynomial-time problems in polynomial time.    (08)

  4. As a useful programming language, Prolog is able to express
     problems that may take exponential time or be undecidable
     for some inputs, but efficiently solvable for other inputs.    (09)

  5. But Prolog can also be very efficient for polynomial-time
     problems.    (010)

  6. In fact, many people translate restricted languages like OWL
     to Prolog in order to make them run faster.    (011)

For more information, see the following article:    (012)

    Fads and fallacies about logic    (013)

John    (014)

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    (015)

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