X-Message-Number: 14984 From: "Pat Clancy" <> Date: Tue, 21 Nov 2000 10:55:50 -0800 Subject: Re: Misconceptions and Ambiguities about Turing Machines Lee Corbin wrote: > 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." A universal TM is not a "special" case, it is the normal case when talking about computers. In fact our prior discussions about computers vs. brains are correct in referring to universal TMs. From the same author, "Shadows of the Mind", p. 66: "Although a modern computer's detailed internal construction is very different from this (and its internal 'working space', although very large, is not infinite like a Turing machine's idealized tape), all modern general-purpose computers are, in effect, actually universal Turing machines." Pat Clancy Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=14984