Re: Turing machines, quantum computers, and alephs

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

Date: Wed, 23 Mar 2005 08:41:06 -0000

In article <d1q9t4$2ga7$1@msunews.cl.msu.edu>, stephen@nomail.com
says...
> In sci.math Gerry Quinn <gerryq@deletethisindigo.ie> wrote:
> : In article <1111453497.964842.107290@o13g2000cwo.googlegroups.com>,
> : hack@watson.ibm.com says...
> :> If an infinite initial marking is allowed, the machine becomes strictly
> :> more powerful (rises in the Turing-degree hierarchy). For example, one
> :> could solve the Halting Problem for all ordinary Turing machines by
> :> table lookup!
>
> : Interesting perspective, but not what we're talking about here. And I
> : don't believe it is correct, anyway, because of EXACTLY the same error
> : that I believe I have uncovered, and which provoked this thread.
>
> : If you have marked up the solution to the halting problem for all Turing
> : machines up to a certain finite descriptor size, your tape is finite,
> : and its length is an exponential function of the descriptor size. But
> : if you let the descriptor size rize to infinity (Aleph-0), as you must
> : if you are to cater for "all ordinary Turing machines", then the length
> : needed for the marked tape must rise to the order of 2^(Aleph-0) or
> : Aleph-1. And Aleph-1 marks won't fit on a tape, even an infinite one,
> : because it only has room for Aleph-0 symbols.
>
> You are incorrect. There are Aleph-0 Turing machines, and Aleph-0
> finite inputs. So the number of pairs of machines and inputs is
> Aleph-0*Aleph-0=Aleph-0. A tape with room for Aleph-0 symbols has
> room for the answer to the halting problem for all possible machines
> and inputs.

You are quite right, of course - I was hoping nobody would have replied
this morning before I could redeem my error! Of course it's even easy
to encode each Turing machine as a unique natural number, making my
argument above look particularly silly.

Does that invalidate my entire point about Turing machines and quantum
computers? At first I thought so, but now I'm not so sure. Luckily it
isn't after all 'EXACTLY' my argument, as I said.

For a start, do we know that for every non-halting Turing machine
running on an infinite tape, the abstract quantum computer with infinite
qubits corresponding to the same problem will not halt?

Also, if we are reduced to discussing finite devices, just how relevant
is the Turing-Church thesis to 'computational power' in the first place?
Arguments based on power sets / exponentiation may lose their Cantorian
sting, but they are still highly relevant to what a computing dervice
can do. And it seems to me that there must be a mathematical language
that takes this into account...

- Gerry Quinn

Relevant Pages

  • Re: The Demise of Computationalism?
    ... anyone would actually implement the thing as a Turing Machine. ... It remains to be seen whether UTMs simulate ordinary TMs by executing programs. ... I think you make an important conceptual point: there are significant differences in the way UTMs produce their output vis a vis the way ordinary digital computers do. ... The class of UTMs are just regular old Turing Machines that happen to have ...
    (comp.ai.philosophy)
  • Re: Turing machines, quantum computers, and alephs
    ... If you have marked up the solution to the halting problem for all Turing ... do we know that for every non-halting Turing machine ... is the Turing-Church thesis to 'computational power' in the first place? ...
    (sci.math)
  • Re: Troll-debility sets in [was: What is the Result from Invoking this Halt Function?]
    ... On Sun, 22 Aug 2004 07:22:49 GMT, Owen Jacobson ... >Consider an asychronous keyboard handler triggered by a hardware ... >the definition of a Turing machine. ... There are a number of things that can be done with computers that ...
    (comp.theory)
  • Re: Troll-debility sets in [was: What is the Result from Invoking this Halt Function?]
    ... On Sun, 22 Aug 2004 07:22:49 GMT, Owen Jacobson ... >Consider an asychronous keyboard handler triggered by a hardware ... >the definition of a Turing machine. ... There are a number of things that can be done with computers that ...
    (sci.logic)
  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (comp.theory)