Interestingly, if you take
two difference RDB's and try to reason over both at the same time - you will
find a lot of queries un-decidable.
I don't follow your reasoning on this one. Why would two RDBs have a
different reasoning mechanism, situation description, or otherwise any
difference at all between the two RDBs? I am somehow missing your meaning and
yet I think you have something important to say here. Can you state it more clearly
Rich AT EnglishLogicKernel DOT com
[mailto:ontolog-forum-bounces@xxxxxxxxxxxxxxxx] On Behalf Of Len Yabloko
Sent: Sunday, December 27, 2009 6:56 PM
Subject: Re: [ontolog-forum] blogic iswc keynote
Thank you to everyone for very interesting discussion
>I think there is quite an important point at stake here.
>The real issue seems to me not whether one can pick holes in the
>John's points (however much fun that is!), but whether the overall
>has any meat on it.
>That is why if I were to accept, for the sake of this argument,
>dissection of the points below, then I would feel you still do not
get us to
>quite where you would want us to be. That something relevant has
>out. (And that you have not been charitable enough to John.)
>I assume it is a relatively un-contentious point that most business
>building practitioners would be surprised to hear that (logical)
>intractability is anything other than a theoretical problem when
>systems. Many of the IT architects, designers and programmers I
>not even recognise the term. (If anyone disagrees, please let us
>how come they miss such an obvious problem? Maybe, at a practical
>is not a genuine category of problem?
I don't disagree, 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. It is true - some very
fundamental problem like "three body" problem or
"uncertainty" principle did not preclude very successful engineering.
Nor did general undecidability of FOL. 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. Is
that what you call "an illusion of validity"?
>Interestingly the google test on "business systems
>results where intractability is about complexity rather than logic.
>Now maybe you can argue that business system practice is not
>for KE on the semantic web we are (from a practical point of view)
in a new
>situation. And you can see that in this situation (unlike with
>systems) intractability becomes a problem. Maybe that is the way
>argument should go.
I think so too.
>However, I did not see you making that argument. And when/if you
>would need to be a strong enough to give practical reasons why the
>heuristics that have grown up over the last half century when
>business systems cannot be applied successfully in some way to the
>web. I suppose this would involve an explanation of why the two are
I think the main point of contention in this discussion had originated
in questioning applicability of expressive languages (like SQL) to reasoning
over semantic web. And indeed there are many similarities between reasoning in
RDB's and SW. But there is one crucial difference - RDB's are assumed to be
correctly representing the state of the business application. If we remove this
assumption then most of engineering practices around it will fail. I also
believe that this is a stronger assumption than the "closed world
assumption" which only assumes the database to be complete. Together
completeness and correctness of RDB make possible most of practical engineering
approaches. Interestingly, if you take two difference RDB's and try to reason
over both at the same time - you will find a lot of queries un-decidable. This
why practitioners will avoid this at any cost. They would rather merge the
datasets repeatedly (or endlessly which would cost astronomical amounts of
money). Unfortunately, the web can not be continuosly merged. As usual
engineers did find a way around and invented a search engine which is the
closes you come to merged global database index. However, it clear to everyone
that this solution is not satisfactory and temporary.
>My guess is that business systems engineers have developed
heuristics for a
>range of problems where intractability gets bundled in with a large
>of other things and so is not singled out. This is not a new idea.
>Simon (and design science) makes a similar point. Interestingly I
>the outside something similar in action a year or so ago when Hasok
>ophy/dp/0195171276 - who I have mentioned before) was explaining to
>engineers at the Royal Institute of Engineers how scientists
>temperature measurement techniques to avoid awkward complications.
>engineers did not get it as these awkward situations were
>them - and the science was non-standard engineering - as they faced
>problems in real life.
>My guess (and it is no more than a guess) is that while rules of
>(and so intractability) are part of the framework, there are a
>other levels in the framework and all of these contribute to how
>practitioners address the problem. And it seems to me that when
this is all
>in place practitioners have not found logical tractability a useful
>(let me know if my sample is skewed). Now maybe they should, but
>requires an argument that shows their current stance is not
>However, all of this still leaves room for you to argue that the
>web framework is different.
>CM>> Seriously? Only professional mathematicians and
logicians are capable
>> of conceiving, say, the traveling salesman problem?
>Interesting that you chose this example. For Simon and his ilk,
this is an
>example par excellence of design, where the heuristics for getting
>solution work around a complex problem (which may be intractability
>difficult) rather than worry about dealing with it. Where practice
>by economics rather than 'truth'. I guess they would argue this is
>difference between theory and practice.
>I think this needs some more explanation (and I do not have a good
>so if you have the arguments/explanations that show it is practical
>tackle intractability more directly, I would be really interested.
>Otherwise, I guess we have to accept this is something waiting for
>> -----Original Message-----
>> From: ontolog-forum-bounces@xxxxxxxxxxxxxxxx
>> bounces@xxxxxxxxxxxxxxxx] On Behalf Of Christopher Menzel
>> Sent: 23 December 2009 18:47
>> To: [ontolog-forum]
>> Subject: Re: [ontolog-forum] blogic iswc keynote
>> On Dec 18, 2009, at 1:32 PM, "John F. Sowa"
>> > I was talking about the many different ways of using a
>> > a logic, such as FOL. Theorem proving is only one use
>> > In fact, it is probably very far down the list of things
>> > want to do with logic. For example,
>> > 1. Communicate some information -- i.e., transmit an
>> Whose implications for your own knowledge base you might well
>> calculate. Calculating implications is just theorem proving.
>> > 2. Check whether somebody's assertion is consistent with
>> > facts -- i.e., evaluate truth in terms of a specific
>> But in order to be consistent with the facts a statement must
>> consistent simpliciter and the problem of consistency
>> undecidable. Hence, so too is the question of whether a
>> consistent with the facts. Consistency checking, of course,
>> another name for theorem proving.
>> So far your list is illustrating my point.
>> > 6. Check whether a given statement is true of all
>> > -- prove a theorem.
>> Well, that's kind of a misleading way of putting it, since it
>> impossible actually to check all possible models (as you well
>> Rather we (in effect) look for a proof and if we find one,
>> course, it *follows* in virtue of soundness that the statement
>> in all possible models.
>> > Point #6 happens to be a very high priority among
logicians who think
>> that the primary use of logic is to form the foundation for
>> John, I know this is one of your favorite hobby horses, but
>> irrespective of its importance to logicians, point #6 is
surely a (not
>> THE, just A) critical component in the overall vision of the
>> web, as already illustrated in points 1 and 2 above. If I am
>> draw on your knowledge base, I will want to know that your
>> is consistent with mine and I will want to be able to
>> implications of doing so.
>> >>> JFS> The paternalistic approach assumes that
all users are trying
>> to prove a theorem that is valid for all possible models. But
>> people who ask a question are only interested in a specific
>> as the current DB.
>> >> CM> This isn't clear to me at all. If I'm just trying
to describe a
>> certain conceptual domain like, say, human physiology...
>> > First of all, physiology is an experimental science. In
>> development of that science, the most important use for any
>> precise notation (say ordinary language expressed in a way
>> be translated to FOL) is to state observations and form
>> generalizations. That is communication (#1 on the list
>> checking (#2), and induction (#3).
>> >> CM> ... it doesn't seem to me that any inferencing
is done vis-á-vis
>> any sort of fixed finite model.
>> > I have no idea what kind of inferencing you are talking
>> Physiologists aren't the kind of people who state anything in
>> Then I have no idea what *you* are talking about. Of course
>> physiologists don't state things in terms of axioms. Isn't
>> exactly the job of an ontologist? Isn't the whole idea here
>> such information represented formally in terms of a
>> representation language?
>> > They are much more likely to be doing #1, #2, #3, #4, and
>> than #6.
>> At least two of which, as noted, entail #6.
>> > Even physicists state in a tone of derision that they
>> axioms" -- that is in response to things like von
>> quantum mechanics.
>> And ontologists don't "do" cloud chamber
experiments. How is this
>> relevant? Of course physicists "don't do axioms".
They are doing
>> physics; they are not trying to implement the Semantic Web.
>> Ontologists are, so they "do" axioms.
>> > CM> which, if expressed in full FOL, raises the
>> > That possibility is only slightly more likely than the
>> the world will end tomorrow.
>> Huh? You're saying that every "real world" problem
is solvable in
>> polynomial time?
>> > Nobody but a professional mathematician or logician is
>> of "thinking" of an intractable statement, let alone
>> whether it can be proved.
>> Seriously? Only professional mathematicians and logicians are
>> of conceiving, say, the traveling salesman problem? You
>> think that's a real problem for, say, people working in
>> are you really unaware of the problems of intractability in
>> computational biology or molecular dynamics (e.g., protein
>> How about n-body problems in physics and astronomy?
>> > Please note that mathematicians have been using FOL for
>> > They were blissfully unaware of computational complexity
>> > undecidability. Yet it never caused the slightest
problem for them.
>> Well, of course -- those problems didn't *exist*. There was
>> model of computation prior to Turing, and no computers with
>> try to solve mathematically formulable problems, so there were
>> mathematical problems of complexity and undecidability. But
>> > All the FOL statements that Whitehead and Russell stated
>> _Principia Mathamtica_ can be proved in a fraction of a second
>> modern theorem provers.
>> I am frequently amazed at how fast Prover9 and its ilk are
>> solve problems involving multiply-nested quantifiers -- more
>> I had once programmed a tree-based theorem prover on my own as
>> programming exercise that was mostly miserable at solving such
>> problems. However, this is really neither here nor there.
>> not interested in problems that give rise to intractability.
>> their theorems are highly amenable to automated solution
>> > CM> I'm not saying [intractability] can't be managed
-- obviously, it
>> can, if only by putting temporal bounds on searches for proofs
>> countermodels. But that there might be a need to do so if one
>> FOL does need to be expressed.
>> > Yes, such checks should be part of the development
>> Really? Why? I thought intractability is just a concern for
>> professional mathematicians, logicians and other out of touch
>> tower denizens?
>> I agree with you on most matters, John, but your views on
>> intractability mystify me.
>> Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
>> Config Subscr:
>> Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
>> Shared Files: http://ontolog.cim3.net/file/
>> Community Wiki: http://ontolog.cim3.net/wiki/
>> To join:
>> To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx
>Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
>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
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
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