From kragen@dnaco.net Fri Aug 7 13:01:39 1998
Date: Fri, 7 Aug 1998 13:01:37 -0400 (EDT)
From: Kragen
To: Hearer
Subject: Re: Re: Object tag crashes Internet Explorer 4.0
In-Reply-To: <01bdba5d$58b00f20$a954b5cf@default>
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Keywords:
X-UID: 1111
Status: RO
X-Status:
On Tue, 28 Jul 1998, Hearer wrote:
> Several times on bugtraq people have used the words: turing-complete. Could
> you explain what this is?
A Turing machine is a simple automaton which happens to have been
proved to be capable of computing certain functions, and incapable of
computing others. A Turing machine is able to simulate my Pentium, so
it can compute any function my Pentium can calculate, and my Pentium
can easily simulate a Turing machine, so it can compute any function a
Turing machine can calculate, although they would differ widely in
speed. In this sense, my Pentium is equivalent to a Turing machine.
(This is not strictly true, actually, since all real computers have
finite memory, and a Turing machine has conceptually infinite memory,
but as long as you don't run out of memory in your computation, it's
true.)
In this sense, actually, all computers are equivalent to Turing
machines, except possibly for the chips in your wristwatch and your
four-function calculator.
A language in which one can describe how to compute any function a
Turing machine can compute is said to be Turing-equivalent or
Turing-complete.
HTML is not Turing-complete, in that the computations it specifies are
very simple: go to this page. fetch this image. go to this part of
this page. JavaScript is Turing-complete, though.
One of the classical questions about Turing machines is whether a
particular Turing machine will ever finish computing, given a
particular input. It can be proven that it is impossible for another
Turing machine to compute the answer to this question in the general
case, a proof which I can outline for you if you like. (This is the
"halting problem".) Since a Turing machine cannot compute the answer
to this question, there's no way my Pentium can compute it either.
There are simpler automata than Turing machines which can compute some
functions Turing machines can, but not others. Many of these automata
have a general decision procedure that can tell you whether or not they
will ever finish computing, given a particular input. Some examples
are the finite state automaton, the nondeterministic finite state
automaton, the pushdown automaton, and the deterministic pushdown
automaton. HTML lets you express finite state automata, but no more.
I hope this clarifies things instead of muddying them. :)
Kragen