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