John F. Sowa wrote:
> 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.
>
> 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.
>
> 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.
> (01)
This is a good way to characterize the concepts. (02)
> 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 first-order 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).
>
> 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".
>
> Pronouncements like #5 are the kind of scare tactics that
> politicians and talk-show pundits use to strike fear into
> gullible people.
> (03)
John, I think this adds more heat than light. This is not just a "scare
tactic" to keep the DL folk in business. (04)
Unfortunately, it has been my experience that reasoners for untrammeled
languages exhibit a kind of "self-symmetric" behavior. What appears to
be a minor addition or modification to an axiom set can suddenly cause
non-termination on 50 regression tests of the ontology. It is really
hard to know which straw will break the camel's back, even when you
think you know how the reasoner does its searches. (05)
The problem with the use of an "undecidable language" for interlinked
Web ontologies is that you may not know when there has been a minor
addition or modification to one of the ontologies your reasoning engine
is using to answer your queries, with the consequence that everything
that worked yesterday doesn't work today. So there is motive for
considering the "worst possible case" -- on the Internet, you have a
million monkeys with typewriters. (06)
I am a firm believer in expressive power over computational bounding,
but I am not doing anything that absolutely must work next week. I am
only concerned about capturing available knowledge and using it in
certain well-defined patterns to make judgements. And we hope that next
year we will be able to do more with the same knowledge base, using
better engines or more knowledge about how to steer them. (07)
The DL approach constrains what you can write, so that it can guarantee
results. For some projects, that is much more important than allowing
the capture of every nuance. One man's meat is another man's poison. (08)
> 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.
> (09)
Indeed. In most programming languages, however, there are constraints
on what you can express, so that all syntactically valid programs can be
supported by certain implementation patterns. For reasons of that kind
of tractability, for example, a language like Java doesn't allow a class
to be defined as a subclass of more than one other class! In some
sense, DL is to FOL as Java is to LISP -- they both make the capture of
intent easier and more reliable, but constrain the expressions to what a
certain implementation pattern can support.
The difference is that for DL we have a whole set of academic
mathematics to characterize and justify our choices, while the Java
limitations were just engineering choices justified solely by experience. (010)
> 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.
> (011)
Agreed. See above. (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 was EB, not LY.
> 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)
Yes, but now you are talking about the semantics of the relations _you_
are defining and using in the FOL language, not the formal semantics of
the language itself. The intent of my email was to separate exactly
these two ideas. By analogy, it is possible to use Java to formulate
stress analysis, but 'stress' is not a Java concept. (015)
-Ed (016)
--
Edward J. Barkmeyer Email: edbark@xxxxxxxx
National Institute of Standards & Technology
Manufacturing Systems Integration Division
100 Bureau Drive, Stop 8263 Tel: +1 301-975-3528
Gaithersburg, MD 20899-8263 FAX: +1 301-975-4694 (017)
"The opinions expressed above do not reflect consensus of NIST,
and have not been reviewed by any Government authority." (018)
_________________________________________________________________
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 (019)
|