Re: Turing machines, quantum computers, and alephs

From: Peter Webb (webbfamily-diespamdie_at_optusnet.com.au)
Date: 03/19/05 

Date: Sun, 20 Mar 2005 02:42:57 +1100

"Gerry Quinn" <gerryq@DELETETHISindigo.ie> wrote in message
news:MPG.1ca61e3dc9924acb989f53@news.indigo.ie...
>
> This is something that came up on a related thread, but I think it is
> interesting enough to have a thread to itself.
>
> The Church-Turing thesis, i.e. "Every 'function which would naturally be
> regarded as computable' can be computed by a Turing machine." is
> generally regarded as defining the limits of computation. And a Turing
> machine consists of an infinite linear tape on which a read-write head,
> capable of a finite number of states, moves step by step, reading one of
> a finite number of symbols, writing one of them, changing to a
> particular state based on what it read and it's current state, and
> moving in one of two directions or stopping. It is an abstract machine
> that is a good model for electronic computers.
>
> The 'qubit-based' quantum computer works with a set of entangled quantum
> states. Without going into detail, an n-qubit quantum computer can
> theoretically conduct 2^n computations in parallel. That's a lot of
> calculations - for a 300-qubit machine it exceeds the number of atoms in
> the observable universe.
>
> Conventional wisdom is that the Turing machine remains an appropriate
> model for the abstract limit of what a quantum computer is capable of.
> The reasoning is that, no matter how many computations it can do, it is
> still a finite number, and an ordinary machine could do that many if it
> took enough time. Since we're talking about abstract machines, we don't
> care about physical limits such as the size of the universe.
>
> However, when we talk about abstract machines with infinite tapes, we
> need to think about what we mean by 'infinity'. For the Turing machine
> it is straightforward enough - we can place the positions on the tape in
> one-to-one correspondence with the natural numbers. Call this infinity
> Aleph-0. Since the tape head performs any number of sequential
> operations, the number (if I may use the term) of operations the Turing
> machine can perform is Aleph-0.
>
> For the machine corresponding to the abstract quantum computer, we have
> Aleph-0 qubits. But the number of calculations it can do in parallel is
> 2^(Aleph-0), or Aleph-1.
>
> Conclusion: the Turing machine is not after all a valid abstract model
> for the capabilities of a qubit-based quantum computer.
>
> The two functions f(x)=x and f(x)=2^x both reach any finite value of
> f(x). But they don't rise towards the same infinity.
>
> Comments?
>
> - Gerry Quinn
>

Machines which can do more than Turing machines - such as your machine which
performs Aleph 0 simultaneously - are generically known as "Oracle
Machines". A google turned up this page:

http://www.answers.com/main/ntquery;jsessionid=k7esgb2t838u?method=4&dsid=2222&dekey=Hypercomputation&gwp=8&curtab=2222_1&sbid=lc03a

However, it says an infinite qubit machine doesn't implement any more than a
regular Turing Machine, but doesn't say why.

Relevant Pages

  • Turing machines, quantum computers, and alephs
    ... The 'qubit-based' quantum computer works with a set of entangled quantum ... Conventional wisdom is that the Turing machine remains an appropriate ... However, when we talk about abstract machines with infinite tapes, we ... need to think about what we mean by 'infinity'. ...
    (comp.programming)
  • Re: Turing machines, quantum computers, and alephs
    ... an n-qubit quantum computer can ... > Conventional wisdom is that the Turing machine remains an appropriate ... Since we're talking about abstract machines, ... > need to think about what we mean by 'infinity'. ...
    (comp.programming)
  • Turing machines, quantum computers, and alephs
    ... The 'qubit-based' quantum computer works with a set of entangled quantum ... Conventional wisdom is that the Turing machine remains an appropriate ... However, when we talk about abstract machines with infinite tapes, we ... need to think about what we mean by 'infinity'. ...
    (sci.math)
  • Re: Turing machines, quantum computers, and alephs
    ... an n-qubit quantum computer can ... > Conventional wisdom is that the Turing machine remains an appropriate ... Since we're talking about abstract machines, ... > need to think about what we mean by 'infinity'. ...
    (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)
Loading