🚀 go-pugleaf

In article <UedH4ge00WB80CdOB6@andrew.cmu.edu>, Leslie Burkholder <lb0q+@andrew.cmu.edu> writes:
|> Suppose we allow an automaton to have an infinite rather than a finite
|> number of states. Is that (equivalent to) a Turing machine? References,
|> please.
|> Thanks,
|> Leslie Burkholder

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.

This is probably best seen by considering the algebraic way of defining both
finite state machines and Turing machines.

References:

Good old Marvin Minsky: Finite and Infinite Machines, Prentice Hall
Has an example of an infinite state machine for parenthesis checking

Michael Arbib and Ernest Manes: Arrows, Structures And Functors, Academic Press
Chapter 6, sect. 6.3, contains the relevant definition, making the *finite* case
a special case. That is, you could even imagine an automaton with an uncountable
number of states, say one for each real number.........eat that!

Sincerely
Klaus Gaarder@Norwegian Telecom Research.

-- 
    __o   
  _`\<,_  
 (*)/ (*) Claudio Caputti
+++++++++++++++++++++++++++++++++++++++^++++++++++++++++++++++++++++++++++++++
Free will - the result of chaotic amplification of quantum events in the brain.
------------------------------------------------------------------------------

klaus@hal.nta.no (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.


Koen Versmissen
--
OTS, Universiteit Utrecht, Trans 10, 3512 JK  Utrecht, NL
E-mail: Koen.Versmissen@let.ruu.nl - Tel: (+31) 30-536057

In article <versmiss.715952911@ruulo3> versmiss@let.ruu.nl (Koen Versmissen) writes:
>klaus@hal.nta.no (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 
     ^^^^^^^^^^^

By a non-constructive process, no doubt. 


-- 


yodaiken@chelm.cs.umass.edu

lb0q+@andrew.cmu.edu (Leslie Burkholder) writes:

>>Suppose we allow an automaton to have an infinite rather than a finite
>>number of states. Is that (equivalent to) a Turing machine? References,
>>please.
>>Thanks,
>>Leslie Burkholder

  This occurs in cellular automata if you have an infinite state space;
e.g., if you state space is the set of all right half infinite 0,1
sequences (this is my favorite), and it is known that some cellular
automata are equivalent to Turing machines.
  Lots of references abound, but you might check Physica D 45 (1990)
where the entire issue is devoted to CA's.  It gives lots of good
references to past literature as well.
burt