NetNews Usenet Archive 1992 #20/NN_1992_20.iso/spool/sci/logic/1365

Internet Message Format | 1992-09-08 | 2.4 KB

Path: sparky!uunet!gatech!destroyer!ncar!noao!arizona!gudeman
From: [e-mail] (David Gudeman)
Newsgroups: sci.logic
Subject: Re: infinite state automaton
Message-ID: <[e-mail]>
Date: 8 Sep 92 19:59:32 GMT
Organization: U of Arizona CS Dept, Tucson
Lines: 42

In article  <versmiss.715952911@ruulo3> Koen Versmissen writes:
][e-mail] (Klaus Gaarder FNI) writes:

]>A Turing machine can be considered to have an infinite number of
]>states if you define each state by including the contents of the
]>tape in addition to each of the finite number of states, thus giving
]>a countable number of states.
]
]But that doesn't imply that Turing machines are equivalent to ISAs
](Infinite State Automata). After all, assuming a two-letter alphabet,
]just construct an infinite binary branching tree of states and mark
]all and only the states corresponding to words of the language as
]accepting ones. This gives you a deterministic ISA with a countable
]number of states for any language, in particular for non r.e. ones.
]So Turing machines are strictly weaker than ISAs.

How are you going to specify this ifinite number of states?  You can't
specify them exhaustively, but you can do things like make sets of
states that recursively call themselves (which gives you something
evivalent to a PDA).  Or you can add an extra part of the automaton
that lets you push and pop states (which gives you a PDA).  Or you can
add a TM tape, which gives you a TM.

Or you can just have a notation for specifying an infinite number of
simple states, but unless you can come up with a notation more
powerful than any known one, you won't be able to specify the states
constructively.  And what would be the point?  Suppose you have a
problem whose solution you can specify non-constructively, say by the
predicate p.  Now you specify an IFA by saying that for all states,
the state is an accepting state iff the input sequence represents (by
some encoding you choose) a value x for which p(x).

What have you gained?  You certainly haven't proven anything about the
computability or constructiveness of the function.  You haven't given
any clues about how to implement it in the real world.  You haven't
produced anything that will help you decide where the function fits in
the (un)computability hierchary.  Basically, everything that
automatons are good for becomes impossible once you allow this sort of
construction.
--
                    David Gudeman
[e-mail]