[Top] [All Lists]

Re: [ontolog-forum] blogic iswc keynote

To: "[ontolog-forum] " <ontolog-forum@xxxxxxxxxxxxxxxx>
From: Christopher Menzel <cmenzel@xxxxxxxx>
Date: Wed, 30 Dec 2009 10:52:22 -0600
Message-id: <72C773F8-D6D2-499D-8AFA-54FDF8FD9144@xxxxxxxx>
On Dec 29, 2009, at 9:14 AM, John F. Sowa wrote:
> Chris,
> CM> As to why you characterize pointing out weak points in an argument
>> as "picking holes"...    (01)

Just to clarify, this was said in response to Chris Partridge, not you.    (02)

> ...
> What I was objecting to is the repetition of unqualified statements
> like the following, which you just repeated in the most recent note:
> CM> Here, more explicitly, is the basic argument.
>> 1. There is no restriction on the first-order statements one can
>>   use to build an ontology.
>> 2. Consistency/validity/entailment are undecidable in first-order
>>   logic.
>> 3. Therefore, it is possible that questions of consistency/validity
>>   /entailment will be undecidable on the Semantic Web.    (03)

> Qualifications:
>  1. Every major programming language in use today is undecidable
>     in the sense that there can be no general proof that a program
>     written in it will terminate.
>  2. But no programmer would ever dream of asking for a less
>     expressive language.
>  3. For all kinds of computation, including the Semantic Web
>     and relational databases, there is a question that is vastly
>     more important than undecidability or even intractability
>     -- namely, *efficiency* .
>  4. Decidability is usually defined as computable in finite time,
>     and tractable is defined as computable in polynomial time.
>     But when you have millions or billions of data items, any
>     polynomial with an exponent greater than 1 is a disaster.
>  5. If you want an answer within your lifetime, the difference between
>     a thousand years, a billion years, or forever is irrelevant.
> I agree that computational complexity is important for both logic
> and programming.  But we must make it clear that reducing the
> expressive power of a language can *never* solve any problem.
> It merely makes certain problems impossible to state.    (04)

John,    (05)

I agree that these points are very important for filling out the larger 
picture.  I don't want the relatively small points of disagreement between us 
obscure the very large points on which we agree, particularly the fact that it 
is both confused and wrong-headed to think that the way to avoid intractability 
is to tie your hands with an expressively impoverished representation language. 
 That's like choosing to live life as a couch-potato to avoid the risk of 
accident or failure. :-)  And as you rightly point out, and the specter 
intractability, indeed undecidability, already lurks in every Turing complete 
programming language.  I think we disagree only with regard to the extent that 
intractability will need to be addressed in the maintenance, use, and sharing 
of ontologies.    (06)

-chris    (07)

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

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