  We investigate dynamical many-body systems capable of universal computation,
which leads to their properties being unpredictable unless the dynamics is
simulated from the beginning to the end. Unpredictable behavior can be
quantitatively assessed in terms of a data compression of the states occurring
during the time evolution, which is closely related to their Kolmogorov
complexity. We analyze a master equation embedding of classical cellular
automata and demonstrate the existence of a phase transition between
predictable and unpredictable behavior as a function of the random noise
introduced by the embedding. We then turn to have this dynamics competing with
a second process inducing quantum fluctuations and dissipatively driving the
system to a highly entangled steady state. Strikingly, for intermediate
strength of the quantum fluctuations, we find that both unpredictability and
quantum entanglement can coexist even in the long time limit. Finally, we show
that the required many-body interactions for the cellular automaton embedding
can be efficiently realized within a variational quantum simulator platform
based on ultracold Rydberg atoms with high fidelity.
