home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / cellaut / 542 < prev    next >
Encoding:
Text File  |  1992-11-20  |  2.3 KB  |  54 lines
  1. Newsgroups: comp.theory.cell-automata
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!cs.utexas.edu!hellgate.utah.edu!asylum.cs.utah.edu!tolman
  3. From: tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman)
  4. Subject: What is the information content of cellular automata?
  5. Date: 20 Nov 92 16:20:17 MST
  6. Message-ID: <1992Nov20.162017.28766@hellgate.utah.edu>
  7. Organization: University of Utah, CompSci Dept
  8. Lines: 44
  9.  
  10.  
  11.  What is the information content of a particular configuration for a CA?
  12.  What are references which would discuss this? (see below)
  13.  
  14.  
  15.  One could define the information content for a cellular automata to be 
  16. -log(probability of state)  Is this correct?
  17.  
  18.  In S. Amoroso he suggests that the information content
  19. does not change for a reversible deterministic CA, which seems agreeable.
  20. This would also correspond to the above metric, for any later state would
  21. have the same probability as its predecessor. (1)
  22.  
  23.  In T. Toffoli, he suggests that the information content depends
  24. on the initial state for irreversible deterministic CA.  If one has enough
  25. detail to construct the initial state, then one has preserved the information
  26. but if there is not enough to reconstruct then one has lost information. (2)
  27.  
  28.  Wolfram suggests that the "entropy" of a CA can be given by the logarithm
  29. of the "average number of possible states of a system", or as
  30.  
  31.   SUM p(i) log (p(i))
  32.  
  33.   Then he shows a graph with the entropy decreasing for an irreversible
  34. CA, which is based on the probabilities for each of the possible states the
  35. system can be in.....  this is not entirely clear to me, for the INITIAL
  36. state would appear to have an equal distribution, and any later states would
  37. have an unequal probability distribution.. so is he calculating probabilities
  38. on the infinite limit of that state or what? (the alternative is of course
  39. that he calculates the probability for a state from all possible initial
  40. states for a particular time interval)  It appears here that the information
  41. content of a particular state then WOULD be the -log(probability of state) (3)
  42.  
  43.   So what IS the information content of a particular state in a cellular 
  44. automata?
  45.  
  46.  
  47. 1 S. Amoroso, Journal Comp. Sys. Sciences, Vol 6, pp. 448-464.
  48.  
  49. 2 T. Toffoli, Journal Comp. Sys. Sciences, Vol. 15, pp. 213-231
  50.  
  51. 3 S. Wolfram, Rev. Mod. Phys. Vol. 55, No. 3, July 1983, pp. 601-644
  52.  
  53.  
  54.