[Turing] machine 1507
This machine shows in some ways the most complicated behavior of any s = 2, k = 2 Turing machine. As suggested by picture (k) it fails to halt if and only if its configuration at some step matches {(0) ..., {1, 1}, 1, ___} (in the alternative form of page 888). For any input x one can test whether the machine will ever halt using
u[{Reverse[IntegerDigits[x, 2]], 0}]
u[list_] := v[Split[Flatten[list]]]
v[{a_, b_: {}, c_: {}, d_: {}, e_: {}, f_: {}, g___}] := Which[a == {1} || First[a] 0, True, c {}, False, EvenQ[Length[b]], u[{a, 1 - b, c, d, e, f, g}], EvenQ[Length[c]], u[{a, 1 - b, c, 1, Rest[d], e, f, g, 0}], e {} || Length[d] ≥ Length[b] + Length[a] - 2, True, EvenQ[Length[e]], u[{a, b , c, d, f, g}], True, u[{a, 1 - b, c, 1 - d, e, 1, Rest[f], g, 0}]]
This test takes at most n/3 recursive steps, even though the original machine can take of order n2 steps to halt. Among s = 3, k = 2 machines there are 314 machines that do the same computation as 1507, but none any faster.