Notes

Chapter 3: The World of Simple Programs

Section 9: Register Machines


Extended instruction sets [for register machines]

One can consider also including instructions such as

RMExecute[eq[r1_, r2_, m_], {n_, list_}] := If[list[[r1]] == list[[r2]], {m, list}, {n+1, list}] RMExecute[add[r1_, r2_], {n_, list_}] := {n+1, ReplacePart[list, list[[r1]] + list[[r2]], r1]} RMExecute[jmp[r1_], {n_, list_}] := {list[[r1]], list}

Note that by being able to add and subtract only 1 at each step, the register machines shown in the main text necessarily operate quite slowly: they always take at least n steps to build up a number of size n. But while extending the instruction set can increase the speed of operations, it does not appear to yield a much larger density of machines with complex behavior.

From Stephen Wolfram: A New Kind of Science [citation]