Empirical Encounters with Computational Irreducibility and Unpredictability

Hector Zenil, Fernando Soler-Toscano, Joost J. Joosten

There are several forms of irreducibility in computing systems, ranging from undecidability to intractability to nonlinearity. This paper is an exploration of the conceptual issues…