home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / cellaut / 546 < prev    next >
Encoding:
Internet Message Format  |  1992-11-21  |  2.3 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!sdd.hp.com!spool.mu.edu!agate!dog.ee.lbl.gov!ucbvax!bloom-beacon!INTERNET!dont-send-mail-to-path-lines
  2. From: hurd@math.gatech.EDU (Lyman Hurd)
  3. Newsgroups: comp.theory.cell-automata
  4. Subject: Undecidability of configurations/progression
  5. Message-ID: <9211211733.AA15040@math.gatech.edu>
  6. Date: 21 Nov 92 17:33:39 GMT
  7. References: <burt.721505936@aupair.cs.athabascau.ca>
  8. Sender: root@athena.mit.edu (Wizard A. Root)
  9. Distribution: inet
  10. Organization: The Internet
  11. Lines: 46
  12.  
  13. Time for some definitions (sorry I was vague).
  14.  
  15. Let S be a finite set with distinguished (quiescent) element q.
  16.  
  17. Let S^Z (the hat symbol stands for superscript for non-TeX fans) be the set
  18. of doubly infinite sequences of symbols from S.  Hence a configuration c,
  19. is a function c: Z --> S. (Z the integers).
  20.  
  21. Defn 1: A configuration c is finite if there exists M such that c(i)=q for
  22. all i with |i| > M.
  23.  
  24. The next definition may not have been obvious (sorry).
  25.  
  26. Defn 2: A configuration c is periodic (Golze's term) is there exists an M
  27. and a P so that:
  28.  
  29. c(i) = c(i+P) for all |i| > M.
  30.  
  31. probably he should have called these ``eventually periodic''.  If this does
  32. not suffice to explain things, I can sketch a proof.  It is not hard to
  33. show that a finite coniguration need not have a finite predecessor (take
  34. RULE 90 and a configuration consisting of a single non-zero site), and
  35. furthermore some finite configurations can have non-periodic predecessors
  36. (consider the zero map).  But if a finite configuration HAS a predecessor,
  37. it must also have a periodic (in the above sense) predecessor.
  38.  
  39. References:
  40.  
  41. Some of Golze's results appear in:
  42.  
  43. U. Golze, ``Differences between 1- and 2- dimensional cell spaces'' in A.
  44. Lindenmayer and G. Rozenberg (eds), ``Automata, languages, development'',
  45. North-Holland (1976).
  46.  
  47. A more complete set of results appears in his dissertation:
  48.  
  49. U. Golze, ``Endlishe, Periodische, und Rekursive Zellulare Konfigurationen:
  50. Vorgangerberechnung und Garten-Eden-Probleme'' Technische Universitat,
  51. Hannover.
  52.  
  53. (for the mailing list, a refernce apropos my previous mailing on
  54. injectivity and surjectivity)
  55.  
  56. S. Amoroso and Y. N. Patt, ``Decision Procedures for surjectivity and
  57. injectivity of parallel maps for tesselation structures'', J. Comp. Syst.
  58. Sci. 6 (1972) 448-464.
  59.