| Thread Links | Date Links | ||||
|---|---|---|---|---|---|
| Thread Prev | Thread Next | Thread Index | Date Prev | Date Next | Date Index |
1) As you're probably aware, in recent years there has been work on "descriptive complexity" (part of finite model theory) that shows there is a correlation between expressiveness complexity and computing complexity. Cf. Immerman's Descriptive Complexity: http://www.cs.umass.edu/~immerman/descriptive_complexity.html. Also, there is a very good diagram here.
"The complexity of computing a query is closely tied to the complexity of describing the query." (Immerman)
2) Also, the issue you raise in going from an expressive representation to an efficient run-time execution is known as the field of knowledge compilation. I agree that these are two different problems and that both must be addressed. We need very expressive representation languages and very efficient run-time execution.
Cf. http://www.cirl.uoregon.edu/research/knowledgeComp.html:
"Starting with Lipski's ideas about reasoning with deductive databases,
there has been a growing trend aimed at addressing the inherent computational
complexity of many reasoning problems by compiling knowledge bases and/or
queries into restricted forms where query-answering is easier than in the
original language. In this way, computational effort at compile time (presumably
at the system's leisure) can be traded for quick response at query time.
In general,these approaches also involve some form(s) of approximation,
because the target language for the compilation is less expressive than
the original language of the knowledge base."
Also:
A Survey on Knowledge Compilation. Marco Cadoli and Francesco M. Donini.
1997. AI Communications-The European Journal for Artificial Intelligence.
A Knowledge Compilation Map, Adnan Darwiche Pierre Marquis. Journal
of Artificial Intelligence Research 17 (2002) 229-264.
Leo
"John F. Sowa" wrote:
--
BB>... I would say that decidability is not something
> that should be sought at all cost. In fact it seems
> likely that any language sufficient to represent
> anything like the richness of human thought must be
> undecidable.I agree. But I would add that the words "decidable"
and "undecidable" are inappropriate as modifiers of
a language. It is better to use them to characterize
problems.As I said in my first note on this topic, all major
programming languages (C, Ada, Java, C++, C#, Perl,
Python, PHP, LISP, Prolog, etc.) allow programs to
be expressed whose termination is undecidable. But
nobody has ever said that property is a defect.John Sowa