W3C home > Mailing lists > Public > www-rdf-logic@w3.org > April 2002

Re: A Single Foundational Logic for the Semantic Web

From: Pat Hayes <phayes@ai.uwf.edu>
Date: Mon, 29 Apr 2002 09:42:20 -0700
Message-Id: <p0510154cb8ee0eb7aef6@[]>
To: Sandro Hawke <sandro@w3.org>
Cc: www-rdf-logic@w3.org
>There was a battle of intuitions here (a year or so ago), which ended
>up with Pat Hayes convincing me and others that you can't layer logics
>like you layer APIs in a programming language.  You can't define a
>more-expressive logic in a less-expressive logic.  Thus there can be
>no one, single foundational logic. 
>(To wax histrionic: The battle for global interoperability is over;
>it's hopeless.

Well, some of us thought that at the beginning. In my original DAML 
project proposal, I said that we would never get global semantic 
coherence and so should be concentrating on techniques for 
negotiating content between different formats and languages.

>At best, certain communities can agree on some logic
>(eg DAML+OIL) and their software can interoperate.  In some cases,
>mappings can be made between logics, but it's probably wishful
>thinking to expect much from that.)

No, I think that is an exact mirror of the human condition, and 
inevitable in global forum. People talk different languages, but 
manage to get by using patchy translations. If they want to get 
better communications, they have to spend time and effort trying to 
understand more detailed nuances of meaning and differences in 
background assumptions, and so on. Often, they appeal to expert help, 
and may even be willing to pay for it. The SW is likely to have to do 
things like this, if only in a limited and comparatively 'stiff' way 
compared to us human meat-machine geniuses.

>This result has felt wrong to many of us, and I've finally put my
>finger on the counter argument.   It's simple and fairly obvious, but
>I guess it took a year for the theory and programmer parts of by brain
>to talk.
>Put in fairly formal terms:
>     While no logic can completely express the semantics of a more-expressive
>     logic, any Turing-equivalent logic (eg Horn clauses or Java) CAN
>     express any effective inference procedures.  Such procedures guide
>     a computer to do all it ever could do with the (inexpressible)
>     semantics of more-expressive logics.
>In other words,

In other words, you can PROGRAM an inference procedure for any logic 
in, say, LISP or Java (choose your own Turing-complete programming 
language and buy enough memory.)  Sure, of course you can.  But 
that's trivial and irrelevant. It is just a consequence of Church's 
thesis which has got nothing to do with logics in particular. On this 
view of the SW, it can all be done in whatever your favorite 
programming language is. Which is indeed, in some sense, true: 
working code will be written in a programming language on the SW just 
as it is everywhere else.

None of this has anything to do with what the RDF/DAML/OWL 
development effort is about, seems to me.

>if you can get a machine to do something with logic X,
>then you can, in essense, get every machine which understands Horn
>clauses (or Java, or whatever) to do the same thing with logic X.  If
>you can't get a machine to handle logic X, you're really out of luck
>in any case.

The issue is not getting a machine to do something. It is finding a 
way for websites to COMMUNICATE content to one another in a way they 
all in some sense mutually understand. What they DO with that content 
is their business; but in an case, the logics aren't being used to 
communicate methods of doing things (use Java for that), but 
propositions - facts -  about some external world. So the entire idea 
of Turing-Equivalent logic is beside the point. (You don't need N3 to 
do that, by the way. I think Sheffer-stroke propositional logic is 
Turing-complete, given about eight proposition letters.)

>So the layering looks like this:
>    Layer 3: Any logic for which an effective inference procedure is known
>    Layer 2: A Turing-Equivalent Logic (such as TimBL's swap/log [1])
>    Layer 1: RDF (Pat's MT, more or less)
>So: we can and should pick a Turing-Equivalent logic (with an RDF
>syntax) and recommend it as a foundational part of the Semantic Web.
>If we do this, new logics can be defined and used interoperabily at
>will.  Some logics (eg DL, arithmetic) can be recognized by some
>reasoners and handled with better performance.
>I think this view helps explain why some of us keep being unconcerned
>by PFPS's red flags about paradoxes.  The paradoxes do not seem to
>appear at the Turing-Equivalent level (which has no real negation or
>notion of falsehood), and we view paradoxes in Layer 3 as just another
>programming problem.  From a Layer 2 perspective, the worst these
>paradoxes produce is an all-too-familiar non-terminating process.
>(This does not mean the paradoxes are not a big problem, just that
>they're a problem in Layer-3 logics, and some of us are still busy on
>layers 1 and 2.  And....  I'm not convinced Layer 3 will be very

Sandro, I just don't know how to tell you this politely, sorry. You 
are confused.

Look, the paradoxes are not a programming problem, and they don't 
have anything to do with non-termination. (A non-terminating process 
corresponds to something that is undecideable, roughly, not to a 
paradox.) If the SW tried to do reasoning in the presence of 
paradoxes, the problem would not be that code fails to terminate. All 
the reasoning engines would work fine, and if they were using 
DL-style logic then they would probably work quite efficiently and 
rapidly, producing correct, checkable proofs using semantically 
correct inference rules. However, the conclusions would all be 
worthless, because that perfectly valid logic would be able to prove 
that 2+2=5 and the Pope was both a Roman Catholic and also not a 
Roman Catholic, and so on. The problem would not be in the code, but 
in the content of the expressions manipulated by the code. The 
correctness of the code would not guarantee that the conclusions made 
any sense (in fact, it would guarantee that they *didnt* make sense.) 
The conclusions produced by any reasoner are only as good as the 
information it is given. In the presence of paradoxes it can produce 
nonsense all by itself, so any information it handles is potentially 


IHMC					(850)434 8903   home
40 South Alcaniz St.			(850)202 4416   office
Pensacola,  FL 32501			(850)202 4440   fax
Received on Monday, 29 April 2002 12:42:21 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:52:42 GMT