Re: Turing machines, quantum computers, and alephs

From: Timothy Murphy (tim_at_birdsnest.maths.tcd.ie)
Date: 03/21/05 

Date: Mon, 21 Mar 2005 12:50:42 +0000

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

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

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

-- 
Timothy Murphy  
e-mail (<80k only): tim /at/ birdsnest.maths.tcd.ie
tel: +353-86-2336090, +353-1-2842366
s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland

Relevant Pages

  • Re: Turing machines, quantum computers, and alephs
    ... > Then infinity is finite because it can be defined by a finite string? ... > Turing defined a Turing machine as having an infinite tape. ... I wasn't saying anything about a Turing machine which always moves right; ...
    (comp.programming)
  • Re: [EGN] turing completeness
    ... I thought your claim was that NO Turing Machine ... This is because you use the word "infinite" carelessly and in a manner ... >> other TM is the UTM. ... > process is required to prove the impossibility of simulating the UTM. ...
    (comp.programming)
  • Re: Turing Machines and Physical Computation
    ... >>A Turing machine is a kind of state machine. ... Turing states the ink supply is infinite. ... TMs don't compute with reals, ... the imagination for use by abstract constructs (the meaning of machine ...
    (comp.theory)
  • Re: Turing Machines and Physical Computation
    ... >>A Turing machine is a kind of state machine. ... Turing states the ink supply is infinite. ... TMs don't compute with reals, ... the imagination for use by abstract constructs (the meaning of machine ...
    (sci.math)
  • Re: Turing machines, quantum computers, and alephs
    ... >> Turing defined a Turing machine as having an infinite tape. ... the abstract quantum computer with infinitely many qubits might start ...
    (sci.math)
Quantcast