Re: Turing machines, quantum computers, and alephs

From: Gerry Quinn (gerryq_at_DELETETHISindigo.ie)
Date: 03/21/05 

Date: Mon, 21 Mar 2005 19:40:20 -0000

In article <tpz%d.50000$Z14.37890@news.indigo.ie>,
tim@birdsnest.maths.tcd.ie says...
> Gerry Quinn wrote:

> >> >> The whole point of a Turing machine, and of a quantum computer,
> >> >> is that they are finite devices.
> >> >
> >> > Not according to Alan Turing, whom I feel ought to have known.
> >>
> >> They are finite devices in the sense that a machine of either type
> >> can be defined by a finite string.
> >
> > Then infinity is finite because it can be defined by a finite string?
> > Turing defined a Turing machine as having an infinite tape.
 
> You are playing with words.

Only trying to be precise. The fact that something can be defined by a
finite string does not make it finite. But anyway, now it is clear that
this is what you mean by "finite device" in the context above.

> A Turing machine has a finite number of states,
> and at any moment there are a finite number of non-blank symbols
> on the tape.

True, the head has a finite number of states, and at any finite time
only finitely many symbols on the tape are different from their starting
state.

> Your machine has an infinite number of q-bits,
> and is therefore not finite in the sense that I am using the word.

Surely that depends instead on whether the initial settings of the
qubits are finitely describable? The Turing machine has an infinite
number of tape segments, but if it starts with a blank tape, or a tape
containing a certain pattern a million bits long, it is finitely
describable even though the tape has infinitely many zeros. Likewise,
the abstract quantum computer with infinitely many qubits might start
off with all but a million in a standard initial state - in which case
it seems no less finite in your sense than the abstract Turing machine
with its infinite but mostly zeroed tape.

> It is not a quantum computer in the normal sense of that term,
> just as a machine with an infinite number of states
> would not be a Turing machine.

No - both of those statements are correct, but there is no "just as".
We have to consider four entities:

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.)

PTM ("physical Turing machine" - something like a Turing machine but
with a finite tape, or a Turing machine simulation running on a PC. It
can be built in the real world. It is not a Turing machine, because it
doesn't have an infinite tape.)

AQC ("abstract quantum computer" - abstract quantum computer with
infinitely many qubits - an abstract concept that could not be built in
the real world.)

PQC ("physical quantum computer" - a physical device with a certain
number of qubits. It can be built in the real world. It is not an
AQC.)

My AQC is not a PQC, but a machine with an infinite number of states
would not be an ATM or a PTM. An ATM has an infinite tape, not an
infinite number of states.

What you are getting at, of course, is the notion that the infinite tape
of an ATM is somehow legitimate whereas the infinite number of qubits of
a AQC is not. But where is the logic in that? A Turing machine with an
infinite tape is the ultimate abstraction of a series of ordinary
computers with increasing amounts of memory. An AQC with an infinite
collection of qubits is the ultimate abstraction of a series of quantum
computers with increasing numbers of qubits.

Computer with 1000 bits of RAM (buildable)
..Computer with 1E24 bits of RAM (big, but doable in principle)
..Computer with 1E50 bits of RAM (not really possible)
.. (abstract limit)
..Turing Machine with infinite tape (certainly impossible)

Quantum computer with 4 qubits (buildable)
..Quantum computer with 40 qubits (big, but doable in principle)
..Quantum computer with 1E10 qubits (not really possible)
.. (abstract limit)
..Abstract quantum computer with infinite qubits (certainly impossible)

If we are to proceed incrementally using finite machines, why not start
with a finite-tape pseudo-Turing machine with tape length X, and a
finite-qubit quantum computer with X qubits? If this is insufficient to
solve a given problem, we try machines with a tape of length 2X, or 2X
qubits. Unconventional, but it seems a good alternative if you are
unhappy working with abstract infinite devices.

> >> > Suppose we build a Turing machine with the property that the head
> >> > always
> >> > moves right and never stops. How long is the tape of that Turing
> >> > machine? If it is replaced by finite stacks, what total stack size
> >> > will be needed?
> >>
> >> There is a difference between an infinite set
> >> and a finite set of unlimited size.
> >
> > You are saying that the Turing machine that always moves right and never
> > halts does not require an "infinite" tape, but "a finite tape of
> > unlimited size"?
>
> I wasn't saying anything about a Turing machine which always moves right;
> the relevance of which escapes me..

When you referred to a finite set of unlimited size, you were responding
to that very notion.

> What I was saying was that one can speak (and normally does speak)
> of a finite stack, without specifying a maximal size for the stack.

Sure, but that's not really relevant to the Turing machine, which is
defined as having an infinite tape. It's defined that way because, of
course, the head may indeed just keep on going right! Maybe because we
built a simple machine to do that, or maybe because we built it to find
a counter-example to Goldbach's Conjecture and stop, but Goldbach's
Conjecture happens to be true.

> > How big is a finite number of unlimited size? Would
> > it be bigger, for example, than any given finite number? If so, how do
> > you distinguish this concept from that of "infinity"?
>
> You might as well say that if you have a mathematical argument
> about a number n, you must specify in advance how large n can be.
> I can have a proposition about a prime number p
> without considering the set of all primes.

Of course you can. But in this case your number n refers to the length
of the tape of a Turing machine, and in some Turing machines the head
moves to the right and never stops. So I ask again, if you are saying
that the tape length of such a Turing machine is "a finite number of
unlimited size", how you distinguish this concept from infinity?

- Gerry Quinn
  

Relevant Pages

  • Re: Turing machines, quantum computers, and alephs
    ... > number of tape segments, but if it starts with a blank tape, or a tape ... > the abstract quantum computer with infinitely many qubits might start ... > it seems no less finite in your sense than the abstract Turing machine ... > with its infinite but mostly zeroed tape. ...
    (sci.math)
  • Re: Turing machines, quantum computers, and alephs
    ... > number of tape segments, but if it starts with a blank tape, or a tape ... > the abstract quantum computer with infinitely many qubits might start ... > it seems no less finite in your sense than the abstract Turing machine ... > with its infinite but mostly zeroed tape. ...
    (comp.programming)
  • Re: turing completeness
    ... The tape doesn't have to be "infinite", ... Turing machine on a physical computer" you are wrong. ... Formalism was David Hilbert's movement, that claimed that programming, ...
    (comp.programming)
  • Re: A unique number for every "person" - can it be done?
    ... > The Turing machine does not ONLY model the limits of the Princeton ... appropriate theoretical model of a quantum computer. ... pattern was part of a finite or infinite system of consecutive states, ...
    (comp.programming)
  • Re: Turing machines, quantum computers, and alephs
    ... > machine consists of an infinite linear tape on which a read-write head, ... an n-qubit quantum computer can ... > Conventional wisdom is that the Turing machine remains an appropriate ... Since we're talking about abstract machines, ...
    (comp.programming)