Multicolor Turing machines [from 2-color TMs]

Given rules in the form on page 888 for a Turing machine with s states and k colors the following yields an equivalent Turing machine with With[{c = Ceiling[Log[2, k]]}, (3 2^c + 2c - 7) s] states (always less than 6.03 k s) and 2 colors:

TMToTM2[rule_, s_, k_] := # /. MapIndexed[#1  First[#2] &, Union[Map[#〚1, 1〛 &, #]]] &[With[{b = Ceiling[Log[2, k]] - 1}, Flatten[Table[{Table[{Table[{{m, i, n, d}, c}  {{m, Mod[i, 2^{n - 1}], n - 1, d}, Quotient[i, 2^{n - 1}], 1}, {n, 2, b}, {i, 0, 2ⁿ - 1}], Table[{{m, i, 1, d}, c}  {{m, -1, 1, d}, i, d}, {i, 0, 1}], Table[{{m, -1, n, d}, c}  {{m, -1, n + 1, d}, c, d}, {n, b - 1}], {{m, -1, b, d}, c}  {{0, 0, m}, c, d}}, {d, -1, 1, 2}], Table[{{i, n, m}, c}  {{ i + 2ⁿ c, n + 1, m}, c, -1}, {n, 0, b - 1}, {i, 0, 2ⁿ - 1}], With[{r = 2^b}, Table[If[i + r c ≥ k, {}, Cases[rule, ({m, i + r c}  {x_, y_, z_})  {{i, b, m}, c}  {{x, Mod[y, r], b, z}, Quotient[y, r], 1})]], {i, 0, r - 1}]]}, {m, s}, {c, 0, 1}]]]]

Some of these states are usually unnecessary, and in the main text such states have been pruned. Given an initial condition {i, list, n} the initial condition for the 2-color Turing machine is

With[{b = Ceiling[Log[2, k]]}, {i, Flatten[IntegerDigits[list, 2, b]], b n}]