  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.
