Hi John, (01)
You are right, from one perspective. (02)
From another perspective, certain language features can cost
more to develop, to debug, to deploy, or to analyze, in which
case the person measuring those additional costs could
validly call one language more complex than another. This,
of course, has little to do with first or second order logic
or with polynomial time or space for execution. As an example,
let us start with identical languages Y and Z, and then add
Feature F to language Y. Thus, the zombie language Z
has one less feature than language Y (similar to analyzing
consciousness -- let Z be human in every way except
for not being conscious, etc.). Then we measure how quickly
we can describe something in Y or Z, create an algorithm,
or debug an algorithm, or how fast Y and Z execute.
With those measurements, we can, from this perspective,
state that one language Y or Z, is more efficient
than the other. Instead of speed one could consider
the time it takes to debug programs in two languages,
identical except that one of them permits programmers
to directly manipulate pointers and the other does not. (03)
From a second perspective, people almost always
define software semantics to not include speed
of execution. This leads to the problem that
people falsely think response time as not part
of the meaning of a program. However, in many
instances, the response time may constitute almost
the only meaning from running the program. You can
think of many instances, like emergency beacons,
SOS calls on sinking ships, email, web pages,
ad servers, bandwidth limited packet communications,
and LOOPTESTER. Loop tester would detect whether
a program terminates in a finite amount of time;
in practice, since a perfect loop tester cannot
exist, one would terminate it after a certain
amount of time, and the "meaning" of the program
execution would tell us that it did or did not
terminate in that amount of time. Thus, I would
say that we need a framework of describing the
meaning of program that includes execution time. (04)
Mike Brenner (05)
John F. Sowa wrote:
> Leo,
>
> As I keep repeating, complexity is first and foremost a property
> of an algorithm, indirectly a property of a problem, and only
> very, very indirectly a property of a language:
>
> > This is a useful tool for determining the specific complexity
> > of the description logic you are interested in.
>
> Most of those complexity claims are based on the assumption
> that the language is going to be used to prove theorems.
>
> But that is certainly not the case of a logic that is used to
> access a database. For example, the WHERE clause in SQL has
> the expressive power of first-order logic. But when it is
> used to express a query or constraint that is evaluated against
> a relational DB, the worst-case complexity takes polynomial time.
>
> And since most relations in a database are indexed on the key
> field or fields, many queries and constraints can be evaluated
> in logarithmic time.
>
> When talking about complexity, it is essential to keep the purpose
> in mind. People keep saying that language L is efficient or
> inefficient without ever mentioning the all-important question:
>
> Efficient for what purpose?????
>
> John (06)
_________________________________________________________________
Msg Archives: http://ontolog.cim3.net/forum/ontology-summit/
Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontology-summit/
Unsubscribe: mailto:ontology-summit-leave@xxxxxxxxxxxxxxxx
Community Files: http://ontolog.cim3.net/file/work/OntologySummit2007/
Community Wiki: http://ontolog.cim3.net/cgi-bin/wiki.pl?OntologySummit2007
Community Portal: http://ontolog.cim3.net/ (07)
|