Re: A case for HTML as a programming language

From: Michael Mendelsohn (keine.Werbung.1300_at_msgid.michael.mendelsohn.de)
Date: 11/09/04 

Date: Tue, 09 Nov 2004 09:10:28 +0100

"Arthur J. O'Dwyer" schrieb:
> On Tue, 9 Nov 2004, Michael Mendelsohn wrote:

> Steven Rudich does exactly this in his "Great Theoretical Ideas" course
> at CMU. :) This is during the lecture in which he points out that it's
> impossible to tell "from the outside" how many states (pages) a finite
> state machine (website) has, if all the outsider can see is "accept" or
> "reject" (the page text) for the current state (page).

Ah, I've had that bookmarked already, for a time when I've got time.

> > If we are talking about Turing machines with finite memories, i.e.
> > finite tapes,
>
> Ah, but a Turing machine without an infinite tape is not a Turing
> machine! So you mean "If we are talking about finite state machines,"
> and you already said that. ;)

Well, we've discussed this here, and no computer ever made had an
infinite tape...

> > certainly every state of the tape can be included in the
> > set of system states, and HTML would then in theory be no better and no
> > worse than general-purpose programming languages.
>
> Worse, space-wise. :)

That's "in practice", not "in theory". ;)

Actually, come to think of it, it's worse in theory as well, because the
space taken up by the "program" is proportional to the complexity
(thinking "big-O") of the problem.

> > Programs would be quite sizeable ("huge" would still be an
> > understatement), but exceptionally speedy: every operation can be
> > executed with the speed the filesystem takes to look up the link.
>
> Since when are file systems "speedy"?

Since the time the flat directory has been superseded by a tree.

> > For illustration, I've written a small (static) HTML program that sorts
> > 5 numbers. You can see it at www.michael.mendelsohn.de/sort5/ .
>
> All right, now make one that prints its own source code! ;)

I think it could be doable with modern HTML; CSS provides for a
substitution mechanism. See http://www.w3.org/TR/CSS21/generate.html .

Cheers
Michael 

-- 
Still an attentive ear he lent        Her speech hath caused this pain
But could not fathom what she meant   Easier I count it to explain
She was not deep, nor eloquent.       The jargon of the howling main
                 -- from Lewis Carroll: The Three Usenet Trolls

Relevant Pages

  • Re: Is memory-based reasoning more powerful than Turing machine?
    ... A TM's tape length is unbounded, but at any point in the ... The LUT equivalent, an always finite but unbounded size LUT, would need ... If you google "turing machine infinite tape" you will find various ... Machine to begin with an infinite tape. ...
    (comp.theory)
  • Re: Ask an atheist a question
    ... its tape, and it can rewrite those programs as it runs. ... A Turing machine can have an infinite tape (for the ... incarnation and there's not an infinite amount of matter in the ... So the amount of information that the Turing Machine is aware of increases ...
    (uk.religion.christian)
  • Re: What is complexity?
    ... >> necessary to have an infinite tape in a physical Turing machine, ... >> long as the tape can grow. ... the head reaches the end of the finite tape: ... Since a true Turing machine always only uses a finite amount ...
    (talk.origins)
  • Re: Ask an atheist a question
    ... its tape, and it can rewrite those programs as it runs. ... A Turing machine can have an infinite tape (for the ... The amount of information that the Turing ... So the amount of information that the Turing Machine is aware of increases ...
    (uk.religion.christian)
  • Re: [QUIZ] The Turing Machine (#162)
    ... tape = tape ... The Turing Machine ... The three rules of Ruby Quiz 2: ... An infinite tape of memory cells that can hold one character ...
    (comp.lang.ruby)