A Single Foundational Logic for the Semantic Web

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.  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.)

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, 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.

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
important.)

...

This, of course, isn't all that different from:

   Layer 3: Applications Libraries and Programs
   Layer 2: Some bytecode (Java, .NET IL, Parrot)
   Layer 1: XML or jar files

but it does have several distribution properties which make it more
promising for a world-wide system, IMHO.

     -- sandro
    

[1] http://www.w3.org/2000/10/swap/log (add ".n3" for readability, maybe)
    Of this, we really only need log:forSome, log:forAll, log:implies,
    and log:Conjunction.  It's just Horn Clauses reformatted for an
    RDF world.

Received on Thursday, 18 April 2002 14:28:16 UTC