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