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.

Relevant Pages

  • Re: The Modified Halting Problem, Take ??? .
    ... Turing tapes" will not be a set or even a proper class in NAFL, ... each tape itself is an infinite entity. ... They're usually described as potentially infinite or finitely unbounded. ... and there is no last digit of Pi ever computed which one would think ...
    (sci.logic)
  • Re: The Modified Halting Problem, Take ??? .
    ... Turing tapes" will not be a set or even a proper class in NAFL, ... each tape itself is an infinite entity. ... They're usually described as potentially infinite or finitely unbounded. ... down or erasing binary digits one-at-a-time in the cells on a linear ...
    (sci.logic)
  • Re: Turing machines, quantum computers, and alephs
    ... Common confusion between infinite and unbounded, ... usual "unbounded tape" one), one must also state that the initial state ... could solve the Halting Problem for all ordinary Turing machines by ... Since any accepting computation is finite by definition, ...
    (comp.programming)
  • Re: turing completeness
    ... claim that the tape *must* be infinite. ... >>The Turing Machine just needs to be able at will to drive to CompUsa ... computer runs out of memory its operating system aborts the TM ...
    (comp.programming)
  • Re: Computable functions/reals.
    ... can't read every position of an infinite tape. ... Then a Zeno machine becomes a machine that "accelerates ... halted, otherwise, the normal TM never halts. ...
    (sci.logic)