Re: Turing machines, quantum computers, and alephs

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

Date: Tue, 22 Mar 2005 03:08:56 +0000

Gerry Quinn wrote:

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

It is not a question of "legitimacy"..
You are perfectly free to talk of machines with an infinity of q-bits
if you wish, though you should not call them quantum computers
because that term has been reserved for something else.

In the same way, it would be misleading to use the term "Turing machine"
for a machine with an infinite number of states.

To my mind, quantum computers and Turing machines (as usually understood)
belong to a completely different sphere of discussion
to the more general devices you were speaking of.
Technically, the former have finite algorithmic entropy
while the latter have infinite entropy. 

-- 
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: [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)
  • 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 ...
    (comp.programming)