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