Permutation

Turing machine A is a permutation of Turing machine B if they are isomorphic up to permuting (renaming) states, symbols (aside from the blank symbol) and directions. If the start state is not affected by the permutation, then the two TMs are functionally identical and are represented by a single TM in TNF. If the start state is changed, then TM A is functionally identical to TM B started in a different start state. Therefore we can say that an n-state TM has effectively n permutations (or n TNF permutations) one for each choice of start state.

Identifying permutations is very useful during TM analysis, since permutations of a TM tend to have the same behavior aside from precise starting configuration. For example, any inductive rules or closed set proven about the original TM will also apply to the permutation (as long as the permutation TM enters that closed set or rule starting config).

Example

1RB2LC1RC_2LC---2RB_2LA0LB0RA (bbch) permuted to start state C is 1RB0LB0RC_2LC2LA1RA_1RA1LC--- (bbch). Here the permutation is $A\to B\to C\to A$, $1\leftrightarrow 2$ and $L\leftrightarrow R$. For example, the first instruction of the original TM A0 -> 1RB becomes B0 -> 2LC in the second TM.

Tools

Code/Permute.py in https://github.com/sligocki/busy-beaver can be used to list all permutations of a TM.