Re: Turing Machines and Physical Computation

stephen_at_nomail.com
Date: 11/28/04 

Date: 28 Nov 2004 18:28:36 GMT

In sci.math JXStern <JXSternChangeX2R@gte.net> wrote:
: On Sun, 28 Nov 2004 08:52:09 GMT, "Stephen Harris"
: <cyberguard1048-usenet@yahoo.com> wrote:
:>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!
: ...

: Substitute "unbounded" for "infinite" when talking about physical
: machines, then, but one can have a theoretically finite machine
: running in theoretically infinite time to turn out a theoretically
: infinite string, nothing is changed. Yes, folks, you can have a
: theoretically finite machine, let's not forget the simple things.

: In fact, cannot one have a very simple state machine handle pretty
: much unbounded a^n b^n? That occurred to me late last night.

: J.

It depends on what you mean by a 'very simple state machine'.
You need to be able to "remember" how many a's you have
seen. A finite state machine can only remember it has seen
n a's if it has a unique state for that value of n.
You need roughly 2m states to recognize a^n b^n for all n<=m
I am not sure that I would consider that 'very simple'.
It is easy to construct and has a very regular structure but
it has a lot of states.

Stephen

Relevant Pages

  • 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
    ... > 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
    ... > 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. ...
    (comp.theory)
  • Re: Turing Machines and Physical Computation
    ... >can perform infinite operations which means it is an abstraction, ... machines, then, but one can have a theoretically finite machine ... Yes, folks, you can have a ... cannot one have a very simple state machine handle pretty ...
    (comp.theory)
  • Re: Turing Machines and Physical Computation
    ... >can perform infinite operations which means it is an abstraction, ... machines, then, but one can have a theoretically finite machine ... Yes, folks, you can have a ... cannot one have a very simple state machine handle pretty ...
    (sci.math)