X-Message-Number: 14973 Date: Mon, 20 Nov 2000 22:28:56 -0800 From: Lee Corbin <> Subject: Misconceptions and Ambiguities about Turing Machines I have sometimes seem it claimed that a _universal_ Turing machine is one with an infinite tape. This is not correct. A universal Turing machine is a TM that can emulate any other TM. This requires special structure in the universal TM, and a convention for interpreting other TMs. As Penrose writes in The Emperor's New Mind, p.51, "The basic idea is to code the list of instructions for an arbitrary Turing machine T into a string of 0s and 1s that can be represented on a tape. This tape is then used as the initial part of the input for some _particular_ Turing machine U---called a universal Turing machine---which then acts on the remainder of the input just as T would have done." Another item, an ambiguity that also arose in recent discussion, was the description of a Turing machine as a physical device of some sort, e.g., a little box on wheels. I agree that this is in many ways the "ideal" physical device with which to push arguments about computation. But by "Turing machine" many people do not mean a physical implementation. They mean a set of quadruple (or quintuples) which mathematically define the states and actions of a hypothetical device. So sometimes people argue right past each other, with one person thinking of the mathematical abstraction, and others thinking of a real device (however idealized). There is a big difference! One is dead, and the other might possibly be alive, which gets back to the contention of some of us that without causality through time and physics, there can be no consciousness or life (something that I don't think anyone on this list will dispute). Practically everyone on this list will also agree that any really significant computer program could be implemented as an enormous (and doubtlessly universal) mathematical Turing machine. He or she will also agree that any computer running such a program is ideally equivalent to a physical Turing machine, e.g., a little box on wheels with the quadruples built-in that can scan a tape. Lee Corbin Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=14973