Stephen Wolfram, along with many others (predating him):
An example. Note the dates. (A New Kind of Science is from 2002.)
http://csc.ucdavis.edu/~chaos/Publications/JPC-Publications....
Also see:
Chris Langton: https://en.wikipedia.org/wiki/Christopher_Langton
C. Langton, Studying articial life with cellular automata, Physica D 22 (1986) 120–149.
Complexity of Langton’s ant: https://arxiv.org/abs/nlin/0306022
I don't think this is the paper's "finding" at all. Sure, the Game of Life indicates that simple systems can result in complex, emergent behavior. But, exactly for being a simple set of rules, it is trivial to create a Game of Life implementation (or following this paper's definition, to solve the problem of predicting the nth next state, given the current state).
The findings are rather that neural networks, despite its universality and prediction power, have a hard time learning parameters that solve this trivial task using a minimal architecture, so they require a larger amount of parameters or a very good initial set of weights ("lottery ticket").
(Beautiful illustration of the “simple rules” that yield complex behaviors: https://www.wolframphysics.org/visual-summary/dark/)