Shift overflow counter: Difference between revisions
Jump to navigation
Jump to search
(Created page with "'''Shift overflow counter''' is an informal class of Turing machines. A typical Turing machine in this class has the following behavior: * it represents digits as short fixed-length blocks of symbols * it spends most of it's time implementing basic double counter until one of the sides overflows (expands) which leads to changing the offsets of blocks, making them non-valid representations of digits * after “Counter Phase” there is a “Reset Phase” where the conte...") |
(Add notable halting examples.) |
||
| Line 2: | Line 2: | ||
* it represents digits as short fixed-length blocks of symbols | * it represents digits as short fixed-length blocks of symbols | ||
* it spends most of | * it spends most of its time implementing basic double counter until one of the sides overflows (expands) which leads to changing the offsets of blocks, making them non-valid representations of digits | ||
* after “Counter Phase” there is a “Reset Phase” where the contents are “reparsed”, creating a new double counter configuration. The new configuration could lead to halting. | * after “Counter Phase” there is a “Reset Phase” where the contents are “reparsed”, creating a new double counter configuration. The new configuration could lead to halting. | ||
Note: some examples (like the Halthing shift-overflow counters below) use a counter on one side and a [[bouncer]] (sometimes called unary counter) on the other. | |||
== Examples == | == Examples == | ||
* Skelet holdouts: [[Skelet 34]], [[Skelet 33]], [[Skelet 35]], [[Skelet 15]], [[Skelet 26]] | * Skelet holdouts: [[Skelet 34]], [[Skelet 33]], [[Skelet 35]], [[Skelet 15]], [[Skelet 26]] | ||
* | * {{TM|1RB1LD_1RC0RB_1LA0LE_1LC0LA_1RZ1RB}} | ||
* | * {{TM|1RB0RF_1LC1RB_0RD0LB_---0LE_1RE0RA_1RD1RE}} | ||
* [ | * {{TM|1RB1LD_1RC0RB_1LA1LE_1LC0LA_1RZ0RD}} | ||
Halting shift-overflow counters: | |||
* Current longest running [[BB(2,5)]] TM: {{TM|1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ}} | |||
* Current second longest running [[BB(6)]] TM: {{TM|1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA}} | |||
== Related links == | == Related links == | ||
[https://www.sligocki.com/2023/02/02/skelet-34.html] | * [https://www.sligocki.com/2023/02/02/skelet-34.html Skelet #34 is Infinite] | ||
[https://www.sligocki.com/2023/02/05/shift-overflow.html] | * [https://www.sligocki.com/2023/02/05/shift-overflow.html Shift Overflow Counters] | ||
[https://discuss.bbchallenge.org/t/skelet-26-and-15-do-not-halt-coq-proof/183] | * [https://discuss.bbchallenge.org/t/skelet-26-and-15-do-not-halt-coq-proof/183 Skelet #26 and #15 do not halt - Coq proof] | ||
[https://discuss.bbchallenge.org/t/skelet-34-and-35-coq-proof/165] | * [https://discuss.bbchallenge.org/t/skelet-34-and-35-coq-proof/165 Skelet #34 and #35 – Coq proof] | ||
[https://discuss.bbchallenge.org/t/skelet-33-doesnt-halt-coq-proof/180] | * [https://discuss.bbchallenge.org/t/skelet-33-doesnt-halt-coq-proof/180 Skelet #33 doesn’t halt - Coq proof] | ||
[[Category:Stub]] | [[Category:Stub]] | ||
[[Category:Zoology]] | [[Category:Zoology]] | ||
Revision as of 20:30, 5 February 2025
Shift overflow counter is an informal class of Turing machines. A typical Turing machine in this class has the following behavior:
- it represents digits as short fixed-length blocks of symbols
- it spends most of its time implementing basic double counter until one of the sides overflows (expands) which leads to changing the offsets of blocks, making them non-valid representations of digits
- after “Counter Phase” there is a “Reset Phase” where the contents are “reparsed”, creating a new double counter configuration. The new configuration could lead to halting.
Note: some examples (like the Halthing shift-overflow counters below) use a counter on one side and a bouncer (sometimes called unary counter) on the other.
Examples
- Skelet holdouts: Skelet 34, Skelet 33, Skelet 35, Skelet 15, Skelet 26
1RB1LD_1RC0RB_1LA0LE_1LC0LA_1RZ1RB(bbch)1RB0RF_1LC1RB_0RD0LB_---0LE_1RE0RA_1RD1RE(bbch)1RB1LD_1RC0RB_1LA1LE_1LC0LA_1RZ0RD(bbch)
Halting shift-overflow counters:
- Current longest running BB(2,5) TM:
1RB3LA4RB0RB2LA_1LB2LA3LA1RA1RZ(bbch) - Current second longest running BB(6) TM:
1RB1RC_1LC1RE_1LD0LB_1RE1LC_1LE0RF_1RZ1RA(bbch)