- From: Harry Halpin <hhalpin@ibiblio.org>
- Date: Tue, 20 Dec 2005 11:15:03 -1000
- To: www-tag@w3.org
There are good examples of non-Turing complete languages that make sense
to your ordinary programmer on the street, such as regular expressions.
Also, Henry noted with his functionalXML thinking that plain-old linear
pipelines are not Turing complete. Original core SQL i.e. SQL 92/96 is
not Turing complete, but SQL99 (SQL3) is.
I might add that the characterization of functional programming
languages as somehow "less powerful" than procedural languages might
want to be - i.e. "through those that are functional and Turing complete
(Haskell), to those which are unashamedly procedural (Java, Javascript,
C)" - should be rephrased, since this will offend functional programmers
who would argue the *exact* opposite :)
If I remember correctly, you get Turing-completeness is you get
variables and unbounded loops combined with the rather subtle effect of
having having arbitary effects at arbitrary steps in the computation. I
think it's the last requirement that makes proofs of Turing completeness
rather subtle [1].
In general, I think it might be a good having Wenfei Fan take a look at
this (wenfei@inf.ed.ac.uk <mailto:wenfei@inf.ed.ac.uk>). Database
researchers like him care *a lot* about language power and
Turing-completeness, since the last thing they want is a database query
which can't be guaranteed to ever return a result (i.e. why SQL was
originally non-Turing complete). I remember him once proving to me that
XPath 2.0 was Turing complete while XPath 1.0 wasn't, but I cannot
remember the details right now.
If one wanted to talk about SemWeb stuff, one could point out that some
problems are undecideable if even a Turing-complete machine be proved
capable of solving them, and one of these problems is inference in FOL,
while weaker logics like description logics (ala OWL-DL/Lite/RDF Schema)
have decideable inference.
Excellent writing in general!
-harry
[1]http://www.mulberrytech.com/Extreme/Proceedings/html/2004/Kepser01/EML2004Kepser01.html
Tim Berners-Lee wrote:
>
> Noah,
>
> Looks good, in general -- Thank you for doing it.
>
> I had thought Roy had said a Principle was a reasonable epithet here
> - but I may remember wrongly.
>
> The PLP bit was added to the Principles DesignIssues note at revision
> 1.10, in January 2002.
> I'm not sure whether it was taken from a previous location.
>
> I'd like to change the wording of the bit about RDF to not talk about
> RDF in the HTML file
> but compare and HTML file with an RDF file. The business of mixing
> them is a distraction.
>
> As regards SQL and truing completeness, I had assumed that it wasn't
> but then I seem to remember
> being told it was.
>
> Tim
>
>
> Annotations for Principles.html
> ***************
> 1.10 (timbl 12-Jan-02): <!DOCTYPE html PUBLIC "-//W3C//DTD
> HTML 4.01 Transitional//EN"
> 1.10 (timbl 12-Jan-02): "http://www.w3.org/TR/html4/
> loose.dtd">
> 1.1 (timbl 09-Sep-99): <html>
> 1.1 (timbl 09-Sep-99): <head>
> 1.10 (timbl 12-Jan-02): <meta http-equiv="Content-Type"
> content="text/html">
> 1.1 (timbl 09-Sep-99): <title>-- Axioms of Web
> architecture</title>
> 1.9 (timbl 08-Jan-01): <link rel="Stylesheet"
> href="di.css">
> 1.1 (timbl 09-Sep-99): </head>
> 1.1 (timbl 09-Sep-99):
> 1.10 (timbl 12-Jan-02): <body bgcolor="#ddffdd"
> text="#000000" lang="en">
> 1.1 (timbl 09-Sep-99): <address>
> 1.1 (timbl 09-Sep-99): Tim Berners-Lee <br>
> 1.10 (timbl 12-Jan-02): Date: 1998, last change: $Date:
> 2001/01/08 19:23:50 $ <br>
> 1.10 (timbl 12-Jan-02): Status: personal view only.
> Editing status: first draft.
> 1.1 (timbl 09-Sep-99): </address>
> 1.1 (timbl 09-Sep-99):
> 1.1 (timbl 09-Sep-99): <p><a href="./">Up to Design
> Issues</a></p>
> 1.1 (timbl 09-Sep-99):
> 1.2 (timbl 09-Sep-99): <p></p>
> 1.2 (timbl 09-Sep-99): <hr>
> 1.2 (timbl 09-Sep-99):
> 1.2 (timbl 09-Sep-99): <h1>Principles of Design</h1>
> 1.2 (timbl 09-Sep-99):
> 1.8 (timbl 09-Sep-99): <p>Again and again we fall back on
> the folklore of the principles of good
> 1.2 (timbl 09-Sep-99): design. Sometimes I need a URI for
> them so this is started as collection of
> 1.8 (timbl 09-Sep-99): them. I have written about some in
> many places. Principles such as
> 1.10 (timbl 12-Jan-02): <b>simplicity</b> and
> <b>modularity</b> are the stuff of software
> 1.10 (timbl 12-Jan-02): engineering; <b>decentralization</
> b> and <b>tolerance</b> are the life and
> 1.10 (timbl 12-Jan-02): breath of Internet. Brian
> Carpenter has enumerated some principles of design
> 1.10 (timbl 12-Jan-02): of the Net [<a
> href="Architecture.html#carpenter">carpenter</a>]. The third
> 1.10 (timbl 12-Jan-02): pair of ideas I have found
> commonly useful for the Web. I mentioned them in a
> 1.10 (timbl 12-Jan-02): keynote at WWW7 and the note on <a
> href="Evolution.html">Evolvability</a>.</p>
> 1.5 (timbl 09-Sep-99):
> 1.10 (timbl 12-Jan-02): <p>This is largely "motherhood and
> apple pie" but it still needs a home.</p>
> 1.2 (timbl 09-Sep-99):
> 1.4 (timbl 09-Sep-99): <h2><a name="KISS">Simplicity</a></
> h2>
> 1.2 (timbl 09-Sep-99):
> 1.7 (timbl 09-Sep-99): <blockquote>
> 1.7 (timbl 09-Sep-99): <p>"Keep it simple, stupid!"</p>
> 1.7 (timbl 09-Sep-99): </blockquote>
> 1.2 (timbl 09-Sep-99):
> 1.2 (timbl 09-Sep-99): <p>Simplicity is easily to quote
> but often ignored in strange ways. Perhaps
> 1.2 (timbl 09-Sep-99): this is because it is the eye of
> the beholder.</p>
> 1.2 (timbl 09-Sep-99):
> 1.2 (timbl 09-Sep-99): <p>A language which uses fewer
> basic elements to achieve the same power is
> 1.2 (timbl 09-Sep-99): simpler.</p>
> 1.2 (timbl 09-Sep-99):
> 1.2 (timbl 09-Sep-99): <p>Sometimes simplicity is
> confused with 'easy to understand". For example, a
> 1.2 (timbl 09-Sep-99): two-line solution which uses
> recursion is a pretty simple, even though some
> 1.2 (timbl 09-Sep-99): people might find it easier to
> work though a 10-line solution which avoids
> 1.2 (timbl 09-Sep-99): recursion.</p>
> 1.2 (timbl 09-Sep-99):
> 1.2 (timbl 09-Sep-99): <p>In XML, "Processing
> Instructions", those things which start with "<?"
> 1.2 (timbl 09-Sep-99): are <strong>not</strong> simple.
> They look simple, just an extra sort of
> 1.2 (timbl 09-Sep-99): thing in the language, but the
> complicate what was a very clean design of
> 1.2 (timbl 09-Sep-99): elements and attributes, and a
> complication in the underlying syntax is has
> 1.2 (timbl 09-Sep-99): great effect. All specifications
> which refer to XML processing will have to
> 1.2 (timbl 09-Sep-99): figure out what to do about
> processing instructions as well as elements.</p>
> 1.2 (timbl 09-Sep-99):
> 1.2 (timbl 09-Sep-99): <h2><a name="Modular">Modular
> Design</a></h2>
> 1.2 (timbl 09-Sep-99):
> 1.10 (timbl 12-Jan-02): <p>When you design a system, or a
> language, then if the features can be
> 1.10 (timbl 12-Jan-02): broken into relatively loosely
> bound groups of relatively closely bound
> 1.10 (timbl 12-Jan-02): features, then that division is a
> good thing to be made a part of the design.
> 1.10 (timbl 12-Jan-02): This is just good engineering. It
> means that when you want to change the
> 1.10 (timbl 12-Jan-02): system, you can with luck in the
> future change only one part, which will only
> 1.10 (timbl 12-Jan-02): require you to understand (and
> test) that part. This will allow other people
> 1.10 (timbl 12-Jan-02): to independently change other
> parts at the same time. This is just classic
> 1.10 (timbl 12-Jan-02): good software design and books
> have been written about it. The corollary,
> 1.10 (timbl 12-Jan-02): the TOII is less frequently met.</p>
> 1.3 (timbl 09-Sep-99):
> 1.3 (timbl 09-Sep-99): <p>Modular design hinges on the
> simplicity and abstract nature of the
> 1.3 (timbl 09-Sep-99): interface definition between the
> modules. A design in which the insides of
> 1.3 (timbl 09-Sep-99): each module need to know all about
> each other is not a modular design but an
> 1.3 (timbl 09-Sep-99): arbitrary partitioning of the
> bits.</p>
> 1.2 (timbl 09-Sep-99):
> 1.2 (timbl 09-Sep-99): <h2 id="Tolerance">Tolerance</h2>
> 1.2 (timbl 09-Sep-99):
> 1.7 (timbl 09-Sep-99): <blockquote>
> 1.7 (timbl 09-Sep-99): <p>"Be liberal in what you
> require but conservative in what you do"</p>
> 1.7 (timbl 09-Sep-99): </blockquote>
> 1.2 (timbl 09-Sep-99):
> 1.2 (timbl 09-Sep-99): <p>This is the expression of a
> principle which applies pretty well in life,
> 1.2 (timbl 09-Sep-99): (it is a typical UU tenet), and is
> commonly employed in design across the
> 1.2 (timbl 09-Sep-99): Internet.</p>
> 1.2 (timbl 09-Sep-99):
> 1.4 (timbl 09-Sep-99): <p>Write HTML 4.0-strict. Accept
> HTML-4.0-Transitional (a superset of
> 1.4 (timbl 09-Sep-99): strict).</p>
> 1.3 (timbl 09-Sep-99):
> 1.4 (timbl 09-Sep-99): <p>This principle can be
> contentious. When browsers are lax about what they
> 1.4 (timbl 09-Sep-99): expect, the system works better
> but also it encourages laxness on the part of
> 1.4 (timbl 09-Sep-99): web page writers. The principle
> of tolerance does not blunt the need for a
> 1.4 (timbl 09-Sep-99): perfectly clear protocol
> specification which draws a precise distinction
> 1.4 (timbl 09-Sep-99): between a conformance and non-
> conformance. The principle of tolerance is no
> 1.5 (timbl 09-Sep-99): excuse for a product which
> contravenes a standard.</p>
> 1.4 (timbl 09-Sep-99):
> 1.4 (timbl 09-Sep-99): <p></p>
> 1.2 (timbl 09-Sep-99):
> 1.2 (timbl 09-Sep-99): <h2
> id="Decentrali">Decentralization</h2>
> 1.2 (timbl 09-Sep-99):
> 1.3 (timbl 09-Sep-99): <p>This is a principle of the
> design of distributed systems, including
> 1.10 (timbl 12-Jan-02): societies. It points out that any
> single common point which is involved in
> 1.10 (timbl 12-Jan-02): any operation trends to limit the
> way the system scales, and produce a single
> 1.3 (timbl 09-Sep-99): point of complete failure.</p>
> 1.3 (timbl 09-Sep-99):
> 1.3 (timbl 09-Sep-99): <p>Centralization in social
> systems can apply to concepts, too. For example,
> 1.3 (timbl 09-Sep-99): if we make a knowledge
> representation system which requires anyone who uses
> 1.5 (timbl 09-Sep-99): the concept of "automobile" to use
> the term
> 1.3 (timbl 09-Sep-99): "http://www.kr.org/stds/industry/
> automobile" then we restrict the set of uses
> 1.3 (timbl 09-Sep-99): of the system to those for whom
> this particular formulation of what an
> 1.3 (timbl 09-Sep-99): automobile is works. The Semantic
> Web must avoid such conceptual bottlenecks
> 1.10 (timbl 12-Jan-02): just as the Internet avoids such
> network bottlenecks.</p>
> 1.2 (timbl 09-Sep-99):
> 1.4 (timbl 09-Sep-99): <h2><a name="TOII">Test of
> Independent Invention</a></h2>
> 1.8 (timbl 09-Sep-99):
> 1.8 (timbl 09-Sep-99): <blockquote>
> 1.8 (timbl 09-Sep-99): <p>If someone else had already
> invented your system, would theirs work with
> 1.8 (timbl 09-Sep-99): yours?</p>
> 1.8 (timbl 09-Sep-99): </blockquote>
> 1.3 (timbl 09-Sep-99):
> 1.4 (timbl 09-Sep-99): <p>Does this system have to be the
> only one of its kind? This simple thought
> 1.4 (timbl 09-Sep-99): test is described in more detail
> in "<a
> 1.4 (timbl 09-Sep-99):
> href="Evolution.html#TOII">Evolution</a>" in these Design Issues. It is
> 1.4 (timbl 09-Sep-99): modularity inside-out: designing a
> system not to be modular in itself, but to
> 1.4 (timbl 09-Sep-99): be a part of an as-yet unspecified
> larger system. A critical property here is
> 1.10 (timbl 12-Jan-02): that the system tries to do one
> thing well, and leaves other things to other
> 1.4 (timbl 09-Sep-99): modules. It also has to avoid
> conceptual or other centralization, as no two
> 1.5 (timbl 09-Sep-99): modules can claim the need to be
> the unique center of a larger system.</p>
> 1.4 (timbl 09-Sep-99):
> 1.4 (timbl 09-Sep-99): <h2><a name="PLP">Principle of
> Least Power</a></h2>
> 1.4 (timbl 09-Sep-99):
> 1.10 (timbl 12-Jan-02): <p>In choosing computer languages,
> there are classes of program which range
> 1.10 (timbl 12-Jan-02): from the plainly descriptive (such
> as Dublin Core metadata, or the content of
> 1.4 (timbl 09-Sep-99): most databases, or HTML) though
> logical languages of limited power (such as
> 1.10 (timbl 12-Jan-02): access control lists, or
> <em>conneg</em> content negotiation) which include
> 1.10 (timbl 12-Jan-02): limited propositional logic,
> though declarative languages which verge on the
> 1.10 (timbl 12-Jan-02): Turing Complete (PDF) through
> those which are in fact Turing Complete though
> 1.10 (timbl 12-Jan-02): one is led not to use them that
> way (XSLT, SQL) to those which are
> 1.10 (timbl 12-Jan-02): unashamedly procedural (Java, C).</p>
> 1.10 (timbl 12-Jan-02):
> 1.10 (timbl 12-Jan-02): <p>The choice of language is a
> common design choice. The low power end of
> 1.10 (timbl 12-Jan-02): the scale is typically simpler to
> design, implement and use, but the high
> 1.10 (timbl 12-Jan-02): power end of the scale has all the
> attraction of being an open-ended hook
> 1.10 (timbl 12-Jan-02): into which anything can be placed:
> a door to uses bounded only by the
> 1.10 (timbl 12-Jan-02): imagination of the programmer.</p>
> 1.10 (timbl 12-Jan-02):
> 1.10 (timbl 12-Jan-02): <p>Computer Science in the 1960s
> to 80s spent a lot of effort making
> 1.10 (timbl 12-Jan-02): languages which were as powerful
> as possible. Nowadays we have to appreciate
> 1.10 (timbl 12-Jan-02): the reasons for picking not the
> most powerful solution but the least
> 1.10 (timbl 12-Jan-02): powerful. The reason for this is
> that the less powerful the language, the
> 1.10 (timbl 12-Jan-02): more you can do with the data
> stored in that language. If you write it in a
> 1.10 (timbl 12-Jan-02): simple declarative from, anyone
> can write a program to analyze it in many
> 1.10 (timbl 12-Jan-02): ways. The Semantic Web is an
> attempt, largely, to map large quantities of
> 1.10 (timbl 12-Jan-02): existing data onto a common
> language so that the data can be analyzed in ways
> 1.10 (timbl 12-Jan-02): never dreamed of by its creators.
> If, for example, a web page with weather
> 1.10 (timbl 12-Jan-02): data has RDF describing that data,
> a user can retrieve it as a table, perhaps
> 1.10 (timbl 12-Jan-02): average it, plot it, deduce things
> from it in combination with other
> 1.10 (timbl 12-Jan-02): information. At the other end of
> the scale is the weather information
> 1.10 (timbl 12-Jan-02): portrayed by the cunning Java
> applet. While this might allow a very cool user
> 1.10 (timbl 12-Jan-02): interface, it cannot be analyzed
> at all. The search engine finding the page
> 1.10 (timbl 12-Jan-02): will have no idea of what the data
> is or what it is about. This the only way
> 1.10 (timbl 12-Jan-02): to find out what a Java applet
> means is to set it running in front of a
> 1.10 (timbl 12-Jan-02): person.</p>
> 1.4 (timbl 09-Sep-99):
> 1.4 (timbl 09-Sep-99): <p>I hope that is a good enough
> explanation of this principle. There are
> 1.4 (timbl 09-Sep-99): millions of examples of the
> choice. I chose HTML not to be a programming
> 1.4 (timbl 09-Sep-99): language because I wanted
> different programs to do different things with it:
> 1.4 (timbl 09-Sep-99): present it differently, extract
> tables of contents, index it, and so on.</p>
> 1.1 (timbl 09-Sep-99):
> 1.1 (timbl 09-Sep-99): <p></p>
> 1.1 (timbl 09-Sep-99):
> 1.5 (timbl 09-Sep-99): <p></p>
> 1.5 (timbl 09-Sep-99): <hr>
> 1.5 (timbl 09-Sep-99):
> 1.5 (timbl 09-Sep-99): <h2><a
> name="References">References</a></h2>
> 1.5 (timbl 09-Sep-99):
> 1.5 (timbl 09-Sep-99): <p><a href="ftp://ftp.isi.edu/in-
> notes/rfc1958.txt" name="carpenter">B.
> 1.5 (timbl 09-Sep-99): Carpenter, Editor: "Architectural
> Principles of the Internet"</a> Internet
> 1.5 (timbl 09-Sep-99): Architecture Board, June 1996,
> RFC1958</p>
> 1.5 (timbl 09-Sep-99):
> 1.5 (timbl 09-Sep-99): <p></p>
> 1.1 (timbl 09-Sep-99):
> 1.2 (timbl 09-Sep-99): <p></p>
> 1.1 (timbl 09-Sep-99):
> 1.1 (timbl 09-Sep-99): <p></p>
> 1.1 (timbl 09-Sep-99): <hr>
> 1.1 (timbl 09-Sep-99):
> 1.1 (timbl 09-Sep-99): <p><a href="Overview.html">Up to
> Design Issues</a></p>
> 1.1 (timbl 09-Sep-99):
> 1.1 (timbl 09-Sep-99): <p><a href="../People/Berners-
> Lee">Tim BL</a></p>
> 1.1 (timbl 09-Sep-99): </body>
> 1.1 (timbl 09-Sep-99): </html>
>
Received on Tuesday, 20 December 2005 21:15:46 UTC