Adjacent
Two Turing machines are adjacent if you can get from one to the other by modifying only one transition and (optionally) applying a permutation. Adjacent TMs are useful to think about at times because they can have similar behavior or follow similar rules. This is definitely not true for all adjacent TMs, but it is in some cases.
Examples
A good example of adjacent TMs are the 5 BB(5) shift overflow counters from Skelet's 43 holdouts:[1]
| Name | Machine |
|---|---|
sk15
|
1RB---_1RC1LB_1LD1RE_1LB0LD_1RA0RC (bbch)
|
sk26
|
1RB1LD_1RC0RB_1LA1RC_1LE0LA_1LC--- (bbch)
|
sk33
|
1RB1LC_0RC0RB_1LD0LA_1LE---_1LA1RE (bbch)
|
sk34
|
1RB1LC_0RC0RB_1LD0LA_1LE---_1LA1RA (bbch)
|
sk35
|
1RB1LC_0RC0RB_1LD0LA_1LE---_1LA0LA (bbch)
|
All of these TMs are adjacent to sk33 via the following changes:
| Name | Change from sk33
|
Start State | Before Permutation | TNF |
|---|---|---|---|---|
sk34
|
E1 -> 1RA
|
A
|
1RB1LC_0RC0RB_1LD0LA_1LE---_1LA1RA
|
1RB1LC_0RC0RB_1LD0LA_1LE---_1LA1RA
|
sk35
|
E1 -> 0LA
|
A
|
1RB1LC_0RC0RB_1LD0LA_1LE---_1LA0LA
|
1RB1LC_0RC0RB_1LD0LA_1LE---_1LA0LA
|
sk26
|
B0 -> 1RE
|
A
|
1RB1LC_1RE0RB_1LD0LA_1LE---_1LA1RE
|
1RB1LD_1RC0RB_1LA1RC_1LE0LA_1LC---
|
sk15
|
B0 -> 1RE
|
D
|
1RB1LC_1RE0RB_1LD0LA_1LE---_1LA1RE
|
1RB---_1RC1LB_1LD1RE_1LB0LD_1RA0RC
|
For sk34 and sk35 the adjacency is easy to see because there is no permutation of states.
Tools
Code/Adjacent.py in https://github.com/sligocki/busy-beaver can be used to list all adjacent TMs.
References
- ↑ Shawn Ligocki. Shift Overflow Counters. 2023. https://www.sligocki.com/2023/02/05/shift-overflow.html