# Binary turing machine group structure -- Taliesin Beynon

Binary turing machine group structure -- Taliesin Beynon

### use permutation group

use permutation group

#### flipping the head is Cycles[{1,2}]

rotating the tape is {Cycles[{1,3,5,7,...,2n-1}], Cycles[{2,4,6,8,2n}] -- this preserves the state of each cell, but moves them all left (or right, whatever, the inverse takes care of that)

flipping the head is Cycles[{1,2}]

rotating the tape is {Cycles[{1,3,5,7,...,2n-1}], Cycles[{2,4,6,8,2n}] -- this preserves the state of each cell, but moves them all left (or right, whatever, the inverse takes care of that)

rotating the tape is {Cycles[{1,3,5,7,...,2n-1}], Cycles[{2,4,6,8,2n}] -- this preserves the state of each cell, but moves them all left (or right, whatever, the inverse takes care of that)

makeBinaryTuringGroup[n_] := PermutationGroup[Cycles[{{1,2}}], Cycles[{Range[1,2n-1,2], Range[2,2n,2]}] ];

#### these are the orders:

these are the orders:

In[]:=

Table[GroupOrder@makeBinaryTuringGroup[i],{i,2,10}]

Out[]=

{8,24,64,160,384,896,2048,4608,10240}

#### plots

plots

In[]:=

CayleyGraph@makeBinaryTuringGroup[3]

Out[]=

In[]:=

CayleyGraph@makeBinaryTuringGroup[4]

Out[]=

#### this sequence is https://oeis.org/A036289

this sequence is https://oeis.org/A036289

The nth order cube-connected cycle can also be constructed as the Cayley graph of the group acting on binary words of length n generated by the group elements that rotate the bits of a word one position left, rotate the bits of a word one position right, and invert the first bit of a word (Akers and Krishnamurthy 1989; Annexstein et al. 1990).

### explicit representation as a semidirect product

explicit representation as a semidirect product

For an infinite tape we model the TM as a semi-direct product of additive structure of (representing head position), and -indexed direct product (representing tape state) whose group multiplication is ⊕ (xor).

The group action is (, ) · (, ) = ( + , ⊕ ( >> )) , in other words: the offsets of two TM actions just add, but the tape effects are XOR’d together after the second is shifted so that it begins where the first action left the tape head. This is a semidirect product since the one subgroup (z) doesn’t “see” the second subgroup, but that one is affected.

The generators are are just (±1, 0) and (0, 1), where the vector 1 there is the element of whose 0’th element is 1, and all other elements are 0.

2

The group action is (

z

1

t

1

z

2

t

1

z

1

z

2

t

1

t

2

z

1

The generators are are just (±1, 0) and (0, 1), where the vector 1 there is the element of

2

####