Hi Dylan and Patrick,

Thanks for the link to the paper by David Deutsch and your quotation from 
it, Dylan. Let me quote from the same section of the paper:

"Computing machines resembling the universal quantum computer could, in 
principle, be built and would have many remarkable properties not 
reproducible by any Turing machine. These do not include the computation of 
non-recursive functions, but they do include 'quantum parallelism', a method 
by which certain probabilistic tasks can be performed faster by a universal 
quantum computer than by any classical restriction of it."

I concede that quantum computing is unprecedentedly fast. However, speed is 
irrelevant concerning Turing machines and other models of computation. If a 
computational model is to distinguish itself from a Turing machine and 
establish its superiority, what it must be capable of is the ability to 
compute things that a Turing machine simply cannot ever compute, regardless 
of (finite) time allowances.

There are, after all, things that no Turing machine will ever compute, 
things that Turing machines are simply incapable of computing. Indeed, 
Turing invented the Turing machine to prove that there are some things that 
no computer will ever compute (which is rather beautiful--I talk about this 
in http://netartery.vispo.com/?p=1174 ).

What David Deutsch is saying in the above quotation is that quantum 
computers are unprecedentedly fast but they are not capable of computing 
anything that a Turing machine cannot compute ("These do not include the 
computation of non-recursive functions"). They compute quicker than previous 
computers, but they do not represent a type of computational model that can 
compute things that Turing machines cannot.

Therefore, quantum computing, as a computational model, may have its 
advantages over Turing's model of computation, but these advantages do not 
invalidate the Church-Turing thesis. That is, quantum computing does not 
represent a type of machine that can, in theory, compute anything that a 
Turing machine cannot.

We have seen computers get faster over the years. Quite a bit faster. And 
smaller. The speed of computers doubles every few years. But we have not 
hailed any of those increases in speed as respresenting a new and superior 
model of computation. The quantum model of computation may be an advance in 
the same way that Leibniz's notation for various things in calculus was 
superior to Newton's, but they were both talking about exactly the same 
theory.

ja

----- Original Message ----- 
From: "Dylan Harris" <[log in to unmask]>
To: <[log in to unmask]>
Sent: Thursday, October 18, 2012 12:03 PM
Subject: Re: David and Jim


Jim, sorry, but you're wrong. Deutsch said, in the abstract to his paper 
that first proposed quantum computers: "Computing machines resembling the 
universal quantum computer could, in principle, be built and would have many 
remarkable properties not reproducible by any Turing machine."

The paper was "Quantum theory, the Church-Turing principle and the universal 
quantum computer", and it can be found here: 
http://www.ceid.upatras.gr/tech_news/papers/quantum_theory.pdf

Dylan

On 17 Oct 2012, at 21:13, Jim Andrews wrote:

> The Turing machine hasn't been redefined, Dylan. It's the same as it was 
> when Turing dreamed it up. Lots has changed, of course, in computing over 
> the last 75 years. But not the Turing machine. It is still the bedrock of 
> the theory of computation.
>
> That quantum computers are fast enough to behave like Turing machines in 
> parallel, Dylan, is simply to say that they behave like Turing machines, 
> because n Turing machines operating in parallel aren't going to compute 
> anything that a single Turing machine can't compute. The quantum device 
> will compute Turing-computable things more quickly, but speed is not at 
> issue.
>
> The question of whether quantum computing is truly a new paradigm of 
> computing involves the question of whether it offers new computations that 
> a Turing machine can never ever (never) compute.
>
> ja
>
> ----- Original Message ----- From: "Dylan Harris" <[log in to unmask]>
> To: <[log in to unmask]>
> Sent: Wednesday, October 17, 2012 10:34 AM
> Subject: Re: David and Jim
>
>
> Well, only because people cheated: the Turing Machine was redefined to 
> accommodate quantum computers. An explanation is here: 
> http://computer.howstuffworks.com/quantum-computer1.htm .
>
> On 17 Oct 2012, at 19:14, Jim Andrews wrote:
>
>> Quantum computing may offer computers of increased speed. We are used to 
>> computers getting faster. What it definitely does not offer is a form of 
>> computing that exceeds the theoretical capabilities of Turing machines.
>>
>> ja
>>
>>> and Jim--yes, all of that scientistic stuff.  We discussed the new age
>>> junk science in the class and and it's a commonplace (as David would
>>> say) to dismiss it and it properly was.  Quantum computing is a whole
>>> different kettle of fish, though. It seems to promise a real
>>> break-through.
>>>
>>>
>>> Jess
>
>
> Dylan Harris
>
> ---
> http://dylanharris.org/
> H +352 2620 1731
> M +352 621 377 160


Dylan Harris

---
http://dylanharris.org/
H +352 2620 1731
M +352 621 377 160