[Top] [All Lists]

Re: [ontolog-forum] OaSM - Incompleteness Is Overrated; Completeness con

To: "'[ontolog-forum] '" <ontolog-forum@xxxxxxxxxxxxxxxx>
From: "Rich Cooper" <rich@xxxxxxxxxxxxxxxxxxxxxx>
Date: Sun, 6 Dec 2009 12:55:28 -0800
Message-id: <20091206205533.39881138D09@xxxxxxxxxxxxxxxxx>

Hi Ferenc,


The statement you made below:

But, importantly, this assumption cannot in fact be implemented in a

reasoning system, as higher-order logics are semantically incomplete:

given any proposed reasoning method for a second- or higher-order

logic, there will be logically valid arguments whose validity cannot it

cannot demonstrated by that method.


There are many, many (in fact MOST practical) applications which don’t require completeness.  For example, SQL has a ‘select’ variant that retrieves the top N rows of an ordered list, thereby converting its query to a beam search.  The purpose of such quick look queries is to investigate feasibility of a solution.  



If the top 100 don’t have anything remotely like the answer you’re seeking,

then mark this part of the search UnSolvable;

else if the top 100 have one or more acceptable answers,

       then take the best one and work it next;

       else if the theory’s top 100 matches have mixed results, then


evaluate each those results;

compare each to results from the other theories returning the top 100 of their own;

  choose the theory with the best <risk/reward/expense/schedule> payoff to open next;




The most obvious example I am familiar with is the time-sensitive data called a “Plot” which is used in radar systems to mark an observation of a signal return with locality information, timestamp, and query to identify which previously known object should have reached that same locality by the same time, within a window.  A beam is sent out; it reflects off a craft; the reflection propagates to the radar receiver; a Plot is sent to the tracking software to see if it can match the query unambiguously against known tracks; if so, plot accepted and matched against a known track, but if not, the Plot may be any combination of:


            An old, weak track that had disappeared for a while, but is now back;

            A brand new track of a previously unknown object;

            A bounce from ground clutter (steel-girded buildings, cars, dentures, …);

            A completely new class of object not previously known to this system;

            An ephemeral signal from no object likely to be of interest to the radar;


The theory and practice of real-time systems is based on knowing precisely when it is “best” to throw away some data, and when it is “best” to keep data and process it.  Sometimes data has to be dropped in nearly every practical system.  That makes nearly every practical system incomplete. 


For example, EVERY web server and EVERY database server is incomplete – there is a timeout associated with every loop to allow for contact being broken at an arbitrary point and subsequent recovery.  So some queries will just not be returned EVER. 


So the notion of incompleteness seems to be almost archaic in modern systems.  It is only important within a very limited scope of an algorithm that must run restrictedly in its own precisely defined environment without taking an learning approach to new conditions it encounters.  





Rich Cooper


Rich AT EnglishLogicKernel DOT com

From: ontolog-forum-bounces@xxxxxxxxxxxxxxxx [mailto:ontolog-forum-bounces@xxxxxxxxxxxxxxxx] On Behalf Of FERENC KOVACS
Sent: Sunday, December 06, 2009 12:26 PM
To: ontolog-forum@xxxxxxxxxxxxxxxx
Subject: Re: [ontolog-forum] Ontologies as social mediators


Chris Menzel wrote:


On Dec 5, 2009, at 10:48 AM, doug foxvog wrote:
> Ferenc wrote:
>> ... I have been trying to visualize the
>> condition where objects, properties and relations change theri character
>> and they become one of the other two as a result of mental operations.
>> ... So jsut a few examples
>> One of these operations is abstraction
>> that helps you see the properties of an object and create a list of such
>> properties.
>> Then by taking one of those properties as an OBJECT, you can go on to
>> define another set of properties.
> This is quite valid.  The issue of "chang[ing] their character" arises from
> the limitations of first order logic.  Computational complexity becomes
> greater when describing properties of properties and reasoning about them.

That is of course true in full higher-order systems but, as noted a
couple of times in this forum by Pat Hayes and others, a system does
not become higher-order in a sense that increases its complexity
simply in virtue of permitting reasoning about properties and
relations.  The complexity of such reasoning increases (from the
semi-decidability of first-order logic to full undecidability) only
under a very strong assumption: that every subset of the domain of an
interpretation is (the extension of) a property; more generally, that
every set of n-tuples of objects in the domain is (the extension of)
an n-place relation.  This is the assumption that, from a purely
theoretical perspective, separates first-order from higher-order
logic.  But, importantly, this assumption cannot in fact be
implemented in a reasoning system, as higher-order logics are
semantically incomplete: given any proposed reasoning method for a
second- or higher-order logic, there will be logically valid argu
ments whose validity cannot it cannot demonstrated by that method.

> In higher-order logic, one can treat relations, classes, and statements
> "relation instances", and instances of classes and make statements about
> them using relations which accept such classes.  The Cyc reasoner has been
> doing this since at least the mid-1990s.

As have many other higher-order systems (as I'm sure you know).  For
the reasons above, however, the implemented reasoning methods for
these systems -- even those whose formal semantics are fully
higher-order -- are theoretically first-order (in the sense that they
are complete relative to a weaker semantics for the systems (so-called
"general semantics", based on the work of Henkin) that abandon the
strong assumption above).  Indeed, some implementations of such
systems (the HOL System, for example) translate the entire system into
an explicit first-order theory to which standard first-order reasoning
methods can then be applied directly.

Chris Menzel

I am certainly not well educated in formal logic, but to me it appears to me that

1) semantics (semantic analyis) should not be constrained to syntax parsing for terminal symbols,

2) reasoning should not be confined to the use of syllogisms in inferences, and
3) computability of valid conclusions by processing chained data base tables should not be a problem provided that a proper GUI is available

4) without verbs as relations the representations of concepts in various networks do not make sense or offer pracical use for people who want to go from one domain to another using a common interface/template that could be provided by relations other than those in use today. You may want to zoom in and out from your 2D representations as opposed to moving in the plane. And to that end you need to be able to change scale in an orderly fashion






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    (01)

<Prev in Thread] Current Thread [Next in Thread>