Re: A case for HTML as a programming language

From: Arthur J. O'Dwyer (ajo_at_nospam.andrew.cmu.edu)
Date: 11/09/04 

Date: Tue, 9 Nov 2004 01:22:40 -0500 (EST)

On Tue, 9 Nov 2004, Michael Mendelsohn wrote:
>
> In a recent thread titled "tree coloring data problem?", to curb
> runtime, Peter Ammon suggested to expand the tree coloring program into
> a giant state machine that would change state based on user input.
> It is certainly conceivable - albeit impractical - to do this in HTML.
> Produce a page for every state the system can have; have each page
> display the state to the user somehow, and depending on what input the
> user selects (i.e. clicks on), the browser executes a state transition.

   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).

> 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. ;)

> 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. :)

> 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"?

> 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! ;)
(Actually, I'm quite curious about this one. If I had any free time,
I'd play with it some more. Googling "html quine" doesn't really help,
of course. I wonder if "HTML programs" are on-topic in comp.text.sgml?)

-Arthur

Relevant Pages

  • Re: Turings Mathematics
    ... I didn't mean an infinite state machine. ... analysed by a Turing machine, ... finite state machine, without the addition of an unbounded tape. ...
    (sci.crypt)
  • Re: Tim Brays Mind
    ... Any real deterministic computer, having finite memory, is not a ... | Turing machine but a state machine. ... No finite run of a Turing machine needs more than a ... finite amount of tape. ...
    (comp.lang.lisp)
  • Re: Tim Brays Mind
    ... > | Turing machine but a state machine. ... state machine not a Turing machine so theorems about ... determining if a state machine will terminate. ... In a sense they are more infinite than Turing ...
    (comp.lang.lisp)
  • Re: Tim Brays Mind
    ... > whether an arbitrary Turing machine will terminate. ... > is trivial to determine if a state machine terminates (simulate it ... > Euclidian algorithm above does terminate and this can be proven. ...
    (comp.lang.lisp)