Len and Chris, (01)
I basically agree with Chris Menzel's comments on Len Yabloko's
note, but I'd like to add a few more comments. (02)
CM> OWL is an attempt to provide a standardized ontology language
> built upon a logical framework in which questions of consistency,
> validity, etc are decidable. In general, such questions are not
> decidable, and that is certainly a limitation, but it predates
> the Semantic Web by several decades. (03)
Computational complexity and decidability are two related subjects
that all programmers should study in their formative years. But
it's important to note the following points: (04)
1. Computational complexity is a property of an algorithm. It
is not directly a property of a problem and certainly not
a property of a language for writing algorithms. (05)
2. It is true that for a given problem, one can talk about the
computational complexity of the *best known* algorithm for
solving that problem. However, this a "squishy" property,
because new algorithms may be discovered and slight changes
to the problem can frequently be solved by algorithms that
are many orders of magnitude more efficient. (06)
3. Decidability is a property of a question. It is not directly
a property of a proposition and certainly not a property of
a language for stating propositions. (07)
4. For example, the same proposition p might be converted
to the question "Is p true in terms of the database D?"
For propositions stated in firstorder logic and any
relational DB, questions of that form can be translated
to SQL and be answered in at worst polynomial time.
But the question "Is p true in terms of every possible
database D?" requires a theorem prover that may answer
very quickly or it may loop forever (undecidable). (08)
5. Those people who attribute decidability to languages are
usually looking at the worst possible case of the worst
possible question for the most complicated possible
proposition. Then they make a blanket pronouncement
that language L is bad because it is "undecidable". (09)
Pronouncements like #5 are the kind of scare tactics that
politicians and talkshow pundits use to strike fear into
gullible people. (010)
The answer to such politicians is that *every* major
programming language is sufficiently expressive to allow
programmers to write intractable or undecidable programs.
And no programmer would *ever* ask for their pet language
to be made less expressive. (011)
The same point is true of knowledge engineers who use
declarative logics. Those who use expressive languages
know how to use them effectively, and nobody who uses
such languages would prefer them to be less expressive. (012)
LY> ... classical formal logic offers only two possible
> interpretations: it is either true or it is false,
> and it cannot be both. (013)
That is true, but it is possible to use classical FOL to
make statements about probabilities and to reason about
the probabilities of other statements in FOL. In that
sense, FOL is being used as a metalanguage to reason
about subjects with a variable degree of probability. (014)
John Sowa (015)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontologforum/
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontologforum/
Unsubscribe: mailto:ontologforumleave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To join: http://ontolog.cim3.net/cgibin/wiki.pl?WikiHomePage#nid1J
To Post: mailto:ontologforum@xxxxxxxxxxxxxxxx (016)
