  In this paper we explore several fundamental relations between formal
systems, algorithms, and dynamical systems, focussing on the roles of
undecidability, universality, diagonalization, and self-reference in each of
these computational frameworks. Some of these interconnections are well-known,
while some are clarified in this study as a result of a fine-grained comparison
between recursive formal systems, Turing machines, and Cellular Automata (CAs).
In particular, we elaborate on the diagonalization argument applied to
distributed computation carried out by CAs, illustrating the key elements of
G\"odel's proof for CAs. The comparative analysis emphasizes three factors
which underlie the capacity to generate undecidable dynamics within the
examined computational frameworks: (i) the program-data duality; (ii) the
potential to access an infinite computational medium; and (iii) the ability to
implement negation. The considered adaptations of G\"odel's proof distinguish
between computational universality and undecidability, and show how the
diagonalization argument exploits, on several levels, the self-referential
basis of undecidability.
