From kragen@dnaco.net Thu Aug 27 07:20:21 1998 Date: Thu, 27 Aug 1998 07:20:19 -0400 (EDT) From: Kragen To: hugi-compo@makelist.com Subject: Re: Turing machines Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Keywords: X-UID: 1476 Status: O X-Status: Well, I thought that this would be of little interest to the list, but with you folks, I should have known that, with this list, *everyone* would ask what a Turing machine was. Here's a brief explanation. (This was in response to a Microsoft employee claiming that it was impossible to detect infinitely recursive HTML, because the problem was an instance of the halting problem.) It doesn't explain the mathematical insides (how to build one), just how it relates to the rest of the world. I can describe that, too, if you want. (BTW: the two-line C program I posted a few days ago was a Turing machine.) Kragen -- Kragen Sitaker We are forming cells within a global brain and we are excited that we might start to think collectively. What becomes of us still hangs crucially on how we think individually. -- Tim Berners-Lee, inventor of the Web ---------- Forwarded message ---------- Date: Fri, 7 Aug 1998 13:01:37 -0400 (EDT) From: Kragen To: Hearer Subject: Re: Re: Object tag crashes Internet Explorer 4.0 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