We develop a theory characterizing the fundamental capability of deep neural
networks to learn, from evolution traces, the logical rules governing the
behavior of cellular automata (CA). This is accomplished by first establishing
a novel connection between CA and Lukasiewicz propositional logic. While binary
CA have been known for decades to essentially perform operations in Boolean
logic, no such relationship exists for general CA. We demonstrate that
many-valued (MV) logic, specifically Lukasiewicz propositional logic,
constitutes a suitable language for characterizing general CA as logical
machines. This is done by interpolating CA transition functions to continuous
piecewise linear functions, which, by virtue of the McNaughton theorem, yield
formulae in MV logic characterizing the CA. Recognizing that deep rectified
linear unit (ReLU) networks realize continuous piecewise linear functions, it
follows that these formulae are naturally extracted from CA evolution traces by
deep ReLU networks. A corresponding algorithm together with a software
implementation is provided. Finally, we show that the dynamical behavior of CA
can be realized by recurrent neural networks.

深度神经网络可以从演化轨迹中学习元胞自动机的逻辑规则，使用 Lukasiewicz 命题逻辑描述了元胞自动机的一般性，并且可以通过连续的分段线性函数和深度 ReLU 网络从元胞自动机的演化过程中提取出相应的公式。