🚀 go-pugleaf

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