You might enjoy A New Kind Of Science.  It is a lavishly illustrated book with copious (Edit: endnotes, not references; thanks to Scott Aaronson's review for helping me see the distinction) centered around the theme of computation and complexity in the behaviour of cellular automata.  Although you might listen to the book's critics before diving into it, I spent a few hours skimming its thousand plus pages and did not regret the time spent.

One can take an automatic (or syntactic) view of your question, as has been done in another worthy read (Goedel, Escher, Bach: An Eternal Golden Braid), where typographical number theory is considered.  An upshot of this is that the provable sentences of such a theory are recursive (a recursive set), while true sentences (those holding in a standard model of the theory) are not recursive (they are recursively enumerable, if I recall correctly).  In order to relate this view to the philosophical aspect of your question, I would want to understand more about how you perceive complexity, but I am confident in suggesting that your perception relates to how simply you can describe a collection of things, and that the technical results say there will be no simple description any time soon.

Apart from the metamathematics involved in recursion theory and studying concepts of descriptive and definable complexities,  I would say that studying behaviour of automata (and more so, engaging in a psychological study of such studies!) is as quick a path to answering your question as any.  An example of this is https://mathoverflow.net/q/243490 , where I take a simple variant of a prime sieve algorithm and ask some number-theoretic questions.  I have not formalized the questions and the study, but I would be surprised if I needed much more than PRA (primitive recursive arithmetic) to carry out such a study.  I think there are even simpler systems whose metamathematics are easily formalized and will yield complexity similar to what you see in number theory.


(Edit: Eternal, not Enigmatic)

Gerhard "Who Will Study The Studier?" Paseman, 2017.10.06.