  Empirical, theoretical and historical aspects of Post's "problem of tag" from
1921 are explored. Evidence of strong computational irreducibility is found.
Despite their deterministic origin, the lengths of successive sequences
generated seem to closely approximate random walks. All 10^25 smallest initial
conditions are found to eventually halt, although sometimes in > 6*10^11 steps.
Implications of the Principle of Computational Equivalence are discussed, along
with examples of identifiable computational capabilities of tag systems.
Various minimal examples of complex behavior are found, including a less-biased
analog of the 3n+1 Collatz problem. There is also discussion of the history of
Emil Post and of tag systems in the context of ideas about the foundations of
mathematics and computation.
