Undecidability in cellular automata

[Undecidability in] natural systems

Undecidability in tiling problems

Computational complexity theory

History [of computational complexity theory]

Lower bounds [on computational complexity]

Functions [computed by Turing machines]

Properties [of example Turing machines]

Longest halting times [in Turing machines]

Growth rates [of halting times]

[NP completeness in] natural systems

Non-deterministic Turing machines

Implementation [of TM cellular automaton]

Satisfiability [emulating Turing machines]

[Intractability in] systems of limited size