home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #20 / NN_1992_20.iso / spool / sci / logic / 1360 < prev    next >
Encoding:
Text File  |  1992-09-08  |  1.8 KB  |  47 lines
  1. Newsgroups: sci.logic
  2. Path: sparky!uunet!mcsun!sunic!aun.uninett.no!nuug!nntp.nta.no!hal.nta.no!klaus
  3. From: klaus@hal.nta.no (Klaus Gaarder FNI)
  4. Subject: Re: infinite state automaton
  5. Message-ID: <1992Sep8.081401.18506@nntp.nta.no>
  6. Sender: news@nntp.nta.no
  7. Nntp-Posting-Host: periferix.nta.no
  8. Organization: Norwegian Telecom Research
  9. References:  <UedH4ge00WB80CdOB6@andrew.cmu.edu>
  10. Date: Tue, 8 Sep 92 08:14:01 GMT
  11. Lines: 34
  12.  
  13. In article <UedH4ge00WB80CdOB6@andrew.cmu.edu>, Leslie Burkholder <lb0q+@andrew.cmu.edu> writes:
  14. |> Suppose we allow an automaton to have an infinite rather than a finite
  15. |> number of states. Is that (equivalent to) a Turing machine? References,
  16. |> please.
  17. |> Thanks,
  18. |> Leslie Burkholder
  19.  
  20. A Turing machine can be considered to have an infinite number of states if you 
  21. define each state by including the contents of the tape in addition to each of
  22. the finite number of states, thus giving a countable number of states.
  23.  
  24. This is probably best seen by considering the algebraic way of defining both
  25. finite state machines and Turing machines.
  26.  
  27. References:
  28.  
  29. Good old Marvin Minsky: Finite and Infinite Machines, Prentice Hall
  30. Has an example of an infinite state machine for parenthesis checking
  31.  
  32. Michael Arbib and Ernest Manes: Arrows, Structures And Functors, Academic Press
  33. Chapter 6, sect. 6.3, contains the relevant definition, making the *finite* case
  34. a special case. That is, you could even imagine an automaton with an uncountable
  35. number of states, say one for each real number.........eat that!
  36.  
  37. Sincerely
  38. Klaus Gaarder@Norwegian Telecom Research.
  39.  
  40. -- 
  41.     __o   
  42.   _`\<,_  
  43.  (*)/ (*) Claudio Caputti
  44. +++++++++++++++++++++++++++++++++++++++^++++++++++++++++++++++++++++++++++++++
  45. Free will - the result of chaotic amplification of quantum events in the brain.
  46. ------------------------------------------------------------------------------
  47.