Re: Turing Machines and Physical Computation

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

Date: Sun, 28 Nov 2004 08:52:09 GMT

"JXStern" <JXSternChangeX2R@gte.net> wrote in message
news:rvciq0d80e28iobi8vbshr73f0gvvtgklc@4ax.com...
> Does a finite machine mean a finite language? Well, even physically
> finite machines can take infinite time to run, and even simple state
> machines can turn out infinite strings in infinite time.
>

That is the point which is being objected to because a physically
finite machine *cannot* take infinite time to run, and no a simple
state machine *cannot* turn out infinite strings in infinite time.

A finite machine cannot do that, only a theoretical machine
can perform infinite operations which means it is an abstraction,
hypothetical, and certainly not physical! TMs come with a
potentially infinite tape, which is why they are theoretical.
Because other apects of a TM can be modeled in a physical
machine (which can only do finite operations) does not change
the TM into a physical machine. TMs and PCs are not the same thing.
Because the TM inspired some of the notions used to build a
physical computer does not give that physical computer all of
theoretical ideas involved in describing the TM. No endless tape
or memory for a PC, and PCs do have a physical time constraint.

This is not a philosophical issue. It is a matter of definitional fact.
It is no more subject to interpretation than parallel lines once
the geometry has been specified.

This point and its consequence only are under dispute. Nobody
is arguing that a finite automata is not a useful concept. Nor is
it a dispute about nominalism. A TM does not exist physically.
It cant exist physically. Most of the ideas used in talking about
the TM exist physically, but not the one under dispute.

Because someone can claim or describe a perpetual motion
machine that works if it is completely without friction does
not mean any physical machine can get around friction.
A TM can avoid friction because it is non-physical
but not a physical computer.

Relevant Pages

  • Re: Turing Machines and Physical Computation
    ... > machines can turn out infinite strings in infinite time. ... finite machine *cannot* take infinite time to run, ... This point and its consequence only are under dispute. ... not mean any physical machine can get around friction. ...
    (sci.math)
  • Re: Turing Machines and Physical Computation
    ... :>finite machine *cannot* take infinite time to run, ... :>state machine *cannot* turn out infinite strings in infinite time. ... theoretically finite machine, let's not forget the simple things. ...
    (comp.theory)
  • Re: Turing Machines and Physical Computation
    ... :>finite machine *cannot* take infinite time to run, ... :>state machine *cannot* turn out infinite strings in infinite time. ... theoretically finite machine, let's not forget the simple things. ...
    (sci.math)