For many cellular automata, it is possible to express the state of a given cell after n iterations as an explicit function of the initial configuration. We say that for such rules the solution of the initial value problem can be obtained. In some cases, one can construct the solution formula for the initial value problem by analyzing the spatiotemporal pattern generated by the rule and decomposing it into simpler segments which one can then describe algebraically. We show an example of a rule when such approach is successful, namely elementary rule 156. Solution of the initial value problem for this rule is constructed and then used to compute the density of ones after n iterations, starting from a random initial condition. We also show how to obtain probabilities of occurrence of longer blocks of symbols.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Solving the Initial Value Problem for Cellular Automata by Pattern Decomposition

  • Henryk Fukś

摘要

For many cellular automata, it is possible to express the state of a given cell after n iterations as an explicit function of the initial configuration. We say that for such rules the solution of the initial value problem can be obtained. In some cases, one can construct the solution formula for the initial value problem by analyzing the spatiotemporal pattern generated by the rule and decomposing it into simpler segments which one can then describe algebraically. We show an example of a rule when such approach is successful, namely elementary rule 156. Solution of the initial value problem for this rule is constructed and then used to compute the density of ones after n iterations, starting from a random initial condition. We also show how to obtain probabilities of occurrence of longer blocks of symbols.