Re: Turing machines, quantum computers, and alephs

stephen_at_nomail.com
Date: 03/23/05 

Date: 22 Mar 2005 23:31:48 GMT

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.

Stephen

Relevant Pages

  • Re: Turing machines, quantum computers, and alephs
    ... machines up to a certain finite descriptor size, your tape is finite, ... if you are to cater for "all ordinary Turing machines", ... And Aleph-1 marks won't fit on a tape, even an infinite one, ... because it only has room for Aleph-0 symbols. ...
    (sci.math)
  • Re: Exploiting limitations of Turing machines in Turing tests?
    ... So it can be useful to abstract them as computing ... machines of some kind, and see just what kind of computing machine they ... there are uncountable infinite number of irrational numbers, ...
    (comp.ai.philosophy)
  • Re: Turing Machines and Physical Computation & TM S REVISIONISTS
    ... >> Postivism implies some sort of physicalism, I think, or at least it ... I do not condone those idealist re-readings of Turing ... > THAT!), THEN, it is absurd to talk of ANY MACHINES WITH INFINITE SIZE. ...
    (comp.theory)
  • Re: Turing Machines and Physical Computation & TM S REVISIONISTS
    ... >> Postivism implies some sort of physicalism, I think, or at least it ... I do not condone those idealist re-readings of Turing ... > THAT!), THEN, it is absurd to talk of ANY MACHINES WITH INFINITE SIZE. ...
    (sci.math)
  • Re: Expert Systems: Is Human Competence Relevant?
    ... The range of frequence is infinite. ... A one-variable blackbox with a complete test suite will take infinite ... Most of "black boxes" of programming envolves dozens of variables, ... small things like making the machines we have today more ...
    (rec.arts.sf.science)
Loading