Re: Turing machines, quantum computers, and alephs

From: Michel Hack (hack_at_watson.ibm.com)
Date: 03/22/05 

Date: 21 Mar 2005 18:01:05 -0800

Gerry Quinn wrote:

> ATM (abstract Turing machine with an infinite tape - what is meant by

> the generic term 'Turing Machine' - an abstract concept that could
not
> be built in the real world.)

Common confusion between infinite and unbounded, I'm afraid. The
critical information that is missing in the summary description above
is that, if one uses the "infinite tape" metaphor (as opposed to the
usual "unbounded tape" one), one must also state that the initial state
of the "infinite" tape has only finitely many marked cells. (On a
two-symbol tape, the initial state has a finite number of 1-bits, for
example.)

If an infinite initial marking is allowed, the machine becomes strictly
more powerful (rises in the Turing-degree hierarchy). For example, one
could solve the Halting Problem for all ordinary Turing machines by
table lookup!

Since any accepting computation is finite by definition, if the initial
tape has only finitely many marked cells, so do all other states
encountered, and hence the same computation could have been carried out
with a finite tape. So the two tape metaphors ("infinite" and
"unbounded") are equivalent in this case.

(In mathematical logic I believe this is called a "compactness"
argument.)

Michel.

Loading