The Decidability Fetish
I received an offline question about the
decidability and practicality of various subsets
of first-order logic for use on the WWW:
> I learned that there are many decidable subsets.
> Thus the relevant question is probably "Which
> of these subsets are practically useful, and
> which are more of academic interest?"
The first point I would make is that decidability
has almost ZERO relevance to practicality. But
some people have a religious belief (i.e., one
that cannot be confirmed or disconfirmed by any
kind of data or any rational argument) that
practical versions of logic must be decidable.
The important question is not decidability (which can
take an exponential amount of time, even for decidable
theories), but scalability. And you cannot answer
that question without knowing N -- the number of items
to which you are going to apply your algorithms.
If N is of the order 10**10, which is the number of
web pages on the Internet, any polynomial with an
exponent greater than 1 is intractable. For example,
if you had an N-squared algorithm, for which each
operation took only 1 nanosecond, 10**20 operations
would take 3000 years.
When we are talking about provability, even for
decidable subsets of logic, we are dealing with
polynomial or even exponential times. So we are not
talking about web-sized databases. The word "web"
in such discussions is a meaningless distraction
used by religious fanatics to call down the wrath
of whatever deity they worship.
The question of decidability is analogous to the
halting problem for programs (i.e., does a program
terminate in a finite time?). For every major
programming language, it is possible to write
programs that cannot be proved to terminate. But
nobody cares -- because good programmers know how
to design good programs. They would never use
a language that was so restricted that it was
impossible to write a nonterminating program.
Exactly the same principle applies to logic.
Good Prolog programmers know very well how to
write efficient programs, and they would never
use a language that was so horribly constrained
that they could not define all the functions
and rules that they needed.
The language I would recommend for writing business
rules that process web data (or any other kind of
data -- since the word "web" is irrelevant to the
design issues) is ordinary Horn-clause logic.
Prolog is an example. Another example would be
one of the more modern versions with typed variables
and with classical negation instead of negation-as-failure.
Some religious fanatics might object that if the
language allowed arbitrary definitions of predicates,
the halting problem would be unprovable or the
decidability would be unprovable. That statement
is correct -- and totally irrelevant. I would
stuff those people back into the teapot.
John Sowa
PS: My recommended way of webifying the notation for
such a logic is to use tags like <script language=Prolog>
... </script>. I would never recommend obfuscating any
reasonable notation for logic with angle brackets.