🚀 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.
------------------------------------------------------------------------------