Adjacent: Difference between revisions
Jump to navigation
Jump to search
(Created page with "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:<ref>Shaw...") |
(→Examples: Removed "non-halt" from bbch-links (does nothing)) Tag: Manual revert |
||
| (3 intermediate revisions by 3 users not shown) | |||
| Line 2: | Line 2: | ||
== Examples == | == Examples == | ||
A good example of adjacent TMs are the 5 [[BB(5)]] [[shift overflow counters]] from [[Skelet's 43 holdouts]]:<ref>Shawn Ligocki. Shift Overflow Counters. 2023. https://www.sligocki.com/2023/02/05/shift-overflow.html</ref> | A good example of adjacent TMs are the 5 [[BB(5)]] [[Shift overflow counter|shift overflow counters]] from [[Skelet's 43 holdouts]]:<ref>Shawn Ligocki. Shift Overflow Counters. 2023. https://www.sligocki.com/2023/02/05/shift-overflow.html</ref> | ||
{| class="wikitable" | {| class="wikitable" | ||
!Name | !Name | ||
| Line 8: | Line 8: | ||
|- | |- | ||
|<code>sk15</code> | |<code>sk15</code> | ||
| | |{{TM|1RB---_1RC1LB_1LD1RE_1LB0LD_1RA0RC}} | ||
|- | |- | ||
|<code>sk26</code> | |<code>sk26</code> | ||
| | |{{TM|1RB1LD_1RC0RB_1LA1RC_1LE0LA_1LC---}} | ||
|- | |- | ||
|<code>sk33</code> | |<code>sk33</code> | ||
| | |{{TM|1RB1LC_0RC0RB_1LD0LA_1LE---_1LA1RE}} | ||
|- | |- | ||
|<code>sk34</code> | |<code>sk34</code> | ||
| | |{{TM|1RB1LC_0RC0RB_1LD0LA_1LE---_1LA1RA}} | ||
|- | |- | ||
|<code>sk35</code> | |<code>sk35</code> | ||
| | |{{TM|1RB1LC_0RC0RB_1LD0LA_1LE---_1LA0LA}} | ||
|} | |} | ||
All of these TMs are adjacent to <code>sk33</code> via the following changes: | All of these TMs are adjacent to <code>sk33</code> via the following changes: | ||
Latest revision as of 19:03, 16 August 2025
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