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[listr1 listr2, {m, list}, {n + 1, list}]

RMExecute[add[r1_, r2_], {n_, list_}] := {n + 1, ReplacePart[list, listr1 + listr2, r1]}

RMExecute[jmp[r1_], {n_, list_}] := {listr1, 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.



Image Source Notebooks:

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