A rewriting rule is a transformation (swap) of a small-ish input graph to small-ish output. Test for a (directed) subgraph isomorphism match of the input, then replace the matched subgraph with the output of the rule, which has the same directed boundary (interface) as the input. Graph Rewriting is an old subject that has a big literature developing in the 1990s [also see the Structure Mapping idea for analogy].

You might notice that such graph rewriting depends on the order in which you make replacements when the input patches overlap, which is quite often, in any slightly dense graph. Wolfram handles this indeterminism by letting all matches happen, and 'branching' the output, into what he calls a multi-way graph. This leads to a mind-boggling explosion in the size of the graph.

Later, he allows paths that converge to the same outcome to recombine. So, if you weren't mind-boggled enough by NP-complete subgraph-isomorphism, followed by combinatorial branching, you now have to add always-and-everywhere subgraph isomorphism to match and collapse common outcomes in the multi-way graph, such that it becomes a DAGgy multiway graph.

That is all assumed, without any explanation, or any worries about NP-completeness, or computational resources. Then he starts his physics project ...

You may have noticed that indeterminism in graph rewriting has a relationship to indeterminism in QM. Branching the multiway graph is a bit like (no really exactly like) the Many Worlds Interpretation of QM.

If you consider rewriting computational steps as clicks of your compute-clock, then time is just distance down the multiway graph. Light cones are just the incoming here-reachable-from relation (past) and reachable-from-here relation (future) regions of your space-time graph. If you slice the graph by local time distance, then you get spacelike separation and physical distance [similar to Causal Graphs and Causal Dynamical Triangulation putative QG theories].

If you look at different converging paths, you get something like the Feynman path-integral formulation of QM. You might think the path integral depends on combining complex numbers, but we haven't mentioned complex numbers yet. In Wolfram's World (TM), the magnitude comes from the number of converging paths, and the phase comes from the different time steps along those paths.

Understanding that fascinating fact was the trigger for me to get Wolfram-curious - it is very interesting that the magnitude and phase of what we think of as complex numbers, can some from the number and length of converging paths in a DAG.

Then energy and momentum (all relativistic 4-vectors?) can be generated by fluxes of various paths through time-like and space-like surfaces cutting the graph. Commuting variables of quantum measurement also come from knowledge within the graph. Then you are off the the races for generating all of physics ... (according to SW) ...