Re: Turing Machines and Physical Computation

From: Stephen Harris (cyberguard1048-usenet_at_yahoo.com)
Date: 11/22/04 

Date: Mon, 22 Nov 2004 01:48:39 GMT

"JXStern" <JXSternChangeX2R@gte.net> wrote in message
news:i342q0tsrbv079f5qqntii9bjfb02fpj1m@4ax.com...
> On Sun, 21 Nov 2004 21:54:26 GMT, "Stephen Harris"
> <cyberguard1048-usenet@yahoo.com>

JXStern wrote:
> Perhaps what I am interested in is a class on the fuzzy boundary
> between FA and UTM, large FA's, equivalent to this here machine I am
> typing on. I suspect many others would be interested in this same
> class, if indeed it is distinguishable in principle from either
> smaller FA's or UTMs. I suppose it is distinguishable, but perhaps
> not interestingly so.
>

I think this is interesting, but I don't know much about it. I also
find the presence or topic of "indistinguishability" interesting.

>>http://plato.stanford.edu/entries/turing-machine/
>>A Turing machine is a kind of state machine.
>>Turing machines are not physical objects but mathematical ones.
>
> Fascinating, a non-physical state machine.
>

The definition of machine is not the usual one that involves something
physical.
In college, an exercise is to use pencil paper and eraser to duplicate
finding
a result of a Turing machine. This produces the same result as if your
computer
simulated a Turing machine. This is an abstract type of machine and it does
not work like a physical machine. I can draw a car, but that doesn't help
me get to the store for groceries, because the car is a physical machine.

> I'm a big fan of SEP, but I believe the idealist interpretation they
> give Turing machines in several articles is inconsistent with what
> Turing wrote, and inconsistent with what he wrote about.

I'm not sure what SEP stands for. I am not aware of anything
which Turing wrote which contradicts my criticism of using
or transferring infinity in an ideal machine to a physical machine.

>

JXStern also wrote:
"But that does not make Turing Machine theory inapplicable
to machines that can be realized."

SH: As far as I know, this has not been claimed, unless Eray
has misrepresented something said which I am not aware of
before I killfiled him.

There is a claim that there is at least one aspect of a Turing machine
which cannot be duplicated by a physical machine, however, and
Turing imagined it and placed it into his thought experiement.

The tape is potentailly infinitely long, because he says it can compute Pi
which is infinite to any degree of accuracy (number of digits).
It will not halt for the reason that it runs out of tape.
Turing states the ink supply is infinite.
The turing machine is given no power supply so it is most like a perpetual
motion idea in terms of continuing energy to move the tape.

I don't think there are any infinite supplies contained within the universe.
So those infinite ideas that he imagined and endowed to his TM are not
going to let you build a physical machine that never runs out of gas for
instance.

PCs that we build need power supplies, and ram which is finite, not a
potentially infinite tape, and a cpu that operates within time. Time is not
mentioned as a factor in Turing's paper. Turing's TM can calculate a
huge number of digits of Pi, way past the capability of a PC that exists
within the physical universe and is constrained by the future of the
universe.

Another way of looking at this is the abstract Super-Turing computers.
PCs must use truncations/approximations of real numbers some of which
are infinitely long. TMs don't compute with reals, the computation would
never get past computing the infinite value of the real needed for the rest
of the computation.

Super-Turing machines are also ideal machines. The theory is that they
are magically hand-waved so that they can perform calculations using
all the digits of a real number, so they infinitely precise and thus have
more power than an ordinary TM. That does not mean that this imagined
capability can be realized in a physically real device/machine. This
discussion
of the capability of TMs vs. Super-TMs is entirely theoretical.

And it is quite implausible that these theoretical capabilities, conferred
by
the imagination for use by abstract constructs (the meaning of machine
as used by Turing) will ever have a physical expression in reality, so this
is closer to magical thinking rather than science.

Other aspects of TMs have a good match with a physically constructed
PC. The ideas translate well. The ideas which involve using infinity in
the operation of your physical machine have no practical implementation.
It has not been observed, and science deals with observed things within
reality certainly more so than the speculation of physical machines endowed
with the power of infinity being built by humans.

That is what my argument with Eray boils down to. I said that because a
TM was an abstract construction which contained the imagined use of
infinity in Turing's thought experiment, that this abstraction* could
perform
a process that could not be done physically. The burden of proof is on
those who want to claim that in the future we can build a physical computer
that uses an infinite anything for the source of its operation (or a part of
it).
*The TM can compute more digits of an otherwise intractable number than
a PC, because it has no time or memory limitation which physical PCs have.

Star Trek time,
Stephen

Relevant Pages

  • Re: [EGN] turing completeness
    ... I thought your claim was that NO Turing Machine ... This is because you use the word "infinite" carelessly and in a manner ... >> other TM is the UTM. ... > process is required to prove the impossibility of simulating the UTM. ...
    (comp.programming)
  • Re: Turing Machines and Physical Computation
    ... >>A Turing machine is a kind of state machine. ... Turing states the ink supply is infinite. ... TMs don't compute with reals, ... the imagination for use by abstract constructs (the meaning of machine ...
    (comp.theory)
  • 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
    ... >> Turing defined a Turing machine as having an infinite tape. ... the abstract quantum computer with infinitely many qubits might start ...
    (comp.programming)
  • Re: Calculus XOR Probability
    ... If a quantitative set is mapped in ascending order from the naturals, ... number of reals on the line. ... to the subsequent logic that claims such a set cannot have infinite values. ... standard orderings, since sets in general don't come with little tags ...
    (sci.math)