Mathematica is the tool that has made possible Stephen Wolfram's exploration of the computational universe, and the emerging field of Wolfram Science (NKS). Whether for modeling, algorithm discovery or basic NKS, Mathematica has immediate built-in capabilities for the systematic study of a broad range of computational systems.
CellularAutomaton — general cellular automaton in 1D, 2D, etc.
TuringMachine — general Turing machine in 1D, 2D, etc.
expr/.rule — apply a rule
NestList — iteratively apply a function or evolution rule
NestWhileList — iterate while checking for looping or termination
ArrayFlatten — flatten out steps in 2D substitution systems, etc.
FindSequenceFunction — find functional forms for integer sequences