Register machines [emulating Turing machines]

Given the rules for a Turing machine in the form used on page 888, a register machine program to emulate the Turing machine can be obtained by techniques analogous to those used in compilers for practical computer languages. Here TMCompile creates a program segment for each element of the Turing machine rule, and TMToRM resolves addresses and links the segments together.

TMToRM[rules_] := Module[{segs, adrs}, segs = Map[TMCompile, rules] ; adrs = Thread[Map[First, rules]  Drop[FoldList[Plus, 1, Map[Length, segs]], -1]]; MapIndexed[(# /. {dr[r_, n_]  d[r, n + First[#2]], dm[r_, z_]  d[r, z /. adrs]})&, Flatten[segs]]]

TMCompile[_  z:{_, _, 1}] := f[z, {1, 2}]

TMCompile[_  z:{_, _, -1}] := f[z, {2, 1}]

f[{s_, a_, _}, {ra_, rb_}] := Flatten[{i[3], dr[ra, -1], dr[3, 3], i[ra], i[ra], dr[3, -2], If[a  1, i[ra], {}], i[3], dr[rb, 5], i[rb], dr[3, -1], dr[rb, 1], dm[rb, {s, 0}], dr[rb, -6], i[rb], dr[3, -1], dr[rb, 1], dm[rb, {s, 1}]}]

A blank initial tape for the Turing machine corresponds to initial conditions {1, {0, 0, 0}} for the register machine. (Assuming that the Turing machine starts in state 1, with a 0 under its head, other initial conditions can be encoded just by taking the values of cells on the left and right to give the digits of the numbers that are initially in the first two registers.) Given the list of successive configurations of the register machine, the steps that correspond to successive steps of Turing machine evolution can be obtained from

(Flatten[Partition[Complement[#, #-1], 1, 2]]&)[Position[list, {_,{_,_,0}}]]

The program given above works for Turing machines with any number of states, but it requires some simple extensions to handle more than two possible colors for each cell. Note that for a Turing machine with s states, the length of the register machine program generated is between 34s and 36s.