Re: A unique number for every "person" - can it be done?

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

Date: Thu, 17 Mar 2005 10:19:12 -0000

In article <1110971378.767646.173070@f14g2000cwb.googlegroups.com>,
spinoza1111@yahoo.com says...
> Gerry Quinn wrote:

> > On the contrary, I understand them quite well. Yes, the Turing
> machine
> > models the limit of a simplified Von Neumann architecture as the CPU
>
> The Turing machine does not ONLY model the limits of the Princeton
> architecture. The Church/Turing thesis, for which no counterexamples
> have been found, is that it models the limits not only of Princeton
> architecture but of all other existent, and conceivable, computer
> architectures.

It does not model an architecture that conducts infinitely many
operations in parallel. And as I have pointed out, this is the more
appropriate theoretical model of a quantum computer.

This is because the parallelism is exponential, and thus rapidly departs
(again, this is theory and I am sceptical) from the limits of a non-
parallel machine time-sharing a number of parallel threads.

> > speed and memory size go to infinity. [Turing was not familiar with
> > the concept of a quantum computer, but he did in fact speculate about
> > computational devices more powerful than a Turing machine.]
>
> (Sigh) (Eye roll) (Crotch grab) The article you showed me ADMITS that
> in the sense Turing intended, the quantum device is NOT more powerful
> than a Turing machine.

It only admits it for pedagogical purposes; it says, in effect, "This
could in principle be simulated on a classical computer - so why are we
saying it is dfferent in kind? Here is why."
 
> > In Cantorian set theory, two raised to the power of an aleph yields a
> > higher aleph. Since we are talking about limiting models, not real
> > physical machines, this is really what is relevant.
>
> Please explain. I don't think you are on to anything. But if you can
> describe genuine mathematical results in terms of a nondenumerable
> Turing machine able (let's say) to partition its tape into unboundedly
> small "squares", and to fill each "square" with a "symbol" consisting
> of a variable and real-valued voltage, which is able to calculate
> something that the ordinary TM cannot, expound by all means.

Since I don't know what a nondenumerable Turing machine is, I'll leave
that to you. What I'm getting at, really, is that infinity isn't a
number, it's a way we talk about limits, or numbers that can't be talked
about, or numbers that can't be identified, or indeed other things. And
the crude infinity of simplistic models can often be better understood
as one of many infinities. In some cases theorems hitherto thought to
refer to infinities can even be used in connection with finite systems.

What you are saying is that the two functions f(x)=x and f(x)=2^x go to
infinity as x does, and that consequently, a limiting model appropriate
to a system growing as x is appropriate to a system that grows as 2^x.
That IS what you claim, in effect. The quantum computer does 16
operations at once, but a classical computer could do 16 in sequence.
The quantum computer does 256 operations at once, but the classical
computer could do 256 in sequence. The quantum computer does 10^150
operations at once, but the classical computer - it can't! They are not
moving towards the same "limit" [the word is not really appropriate,
perhaps some mathematician can give us a better one]. It is your
failure to understand that not all infinities are the same that leads
you to think so.

> Let me be precise. I do not care if the nondenumerable TM is faster.
> The only meaningful question is can it carry out a computation which
> the ordinary TM cannot?

Neither the ordinary Turing machine, nor the machine that would be
appropriate to the ultimate infinate quantum computer can exist. If
they could, the latter would be able to carry out calculations that the
former cannot.

If a physical quantum computer with 500 entangled qubits can be made, it
will be able to carry out calculations that a physical classical
computer the size of the universe cannot. In a finite universe, this is
the difference you get. You cannot expect the theoretical differences
of theoretical infinite machines to be instantiated in the finite
machines of the physical universe. [See also the various debates as to
whether a Turing machine can actually be built.]

> I yam thinking about theoretical compsci given my comprehension of
> same, and as far as I know, Church/Turing holds. It will hold no matter
> how "powerful" computers become because it is refuted by the
> performance of a calculation which cannot be performed by a TM.
>
> Wake me up, in other words, when a qc is able to read the encodement of
> another qc and determine whether that arbitrary qc will HALT.

It would be sufficient if it could determine whether an arbitrary
_Turing_ machine will halt. I am not sure whether this is theoretically
possible. If it could encode every state of the Turing tape and every
bit of the Turing machine state as a qubit, then it seems to me it could
solve the halting problem by determining whether a particular starting
pattern was part of a finite or infinite system of consecutive states,
then separating out the cyclic finite states. But that may be too
ambitious a model.

Not being able to solve a specific problem does not prove there is no
difference.

> Having said this, I do take away the idea that an "analog" TM with
> divisible squares and "symbols" with continuous values might make a
> nifty software simulation. I will get back to you on this.

It's a metaphor, not a model. I was getting at the notion that a real
number can be thought of as an infinite string of decimal digits, and
thus resembles an "infinite integer".

- Gerry Quinn

Relevant Pages

  • Re: A unique number for every "person" - can it be done?
    ... > The Turing machine does not ONLY model the limits of the Princeton ... appropriate theoretical model of a quantum computer. ... pattern was part of a finite or infinite system of consecutive states, ...
    (sci.crypt)
  • 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)
  • 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
    ... > machine consists of an infinite linear tape on which a read-write head, ... an n-qubit quantum computer can ... > Conventional wisdom is that the Turing machine remains an appropriate ... Since we're talking about abstract machines, ...
    (comp.programming)
  • Re: Turing machines, quantum computers, and alephs
    ... > machine consists of an infinite linear tape on which a read-write head, ... an n-qubit quantum computer can ... > Conventional wisdom is that the Turing machine remains an appropriate ... Since we're talking about abstract machines, ...
    (sci.math)