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