Sync bi-counter: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
→Examples: linked Skelet 10 to wiki article |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{Stub}} | |||
A '''sync bi-counter''' is an informal class of Turing machines. A typical Turing machine in this class has the following behavior: | A '''sync bi-counter''' is an informal class of Turing machines. A typical Turing machine in this class has the following behavior: | ||
| Line 6: | Line 7: | ||
== Examples == | == Examples == | ||
* | * {{TM|1LC0LA_---0LC_0RD1LA_1LB1RE_1RD0RE}} (Skelet 10) ([https://www.sligocki.com/2023/03/14/skelet-10.html Proof of non-halt]) | ||
* {{TM|1RB1LA_1LA0RC_1RB0RD_1LE1RD_0LC0LF_---0LA}} | * {{TM|1RB1LA_1LA0RC_1RB0RD_1LE1RD_0LC0LF_---0LA}} | ||
* {{TM|1RB0LE_0LC---_1LA0RD_1RC0RC_1LF1LE_0LA1RF}} | * {{TM|1RB0LE_0LC---_1LA0RD_1RC0RC_1LF1LE_0LA1RF}} | ||
| Line 14: | Line 15: | ||
Inductive decider can deal with some more complex situations. | Inductive decider can deal with some more complex situations. | ||
[[Category:Zoology]] | [[Category:Zoology]] | ||
Latest revision as of 13:19, 21 February 2026
A sync bi-counter is an informal class of Turing machines. A typical Turing machine in this class has the following behavior:
- It has two counters on the tape, and the lowest digit of both counters are adjacent.
- In each round, both of the two counters are increased by one, and they count in the same base. Both counters count to the same number after each round (i.e. they are synchronized).
Examples
1LC0LA_---0LC_0RD1LA_1LB1RE_1RD0RE(bbch) (Skelet 10) (Proof of non-halt)1RB1LA_1LA0RC_1RB0RD_1LE1RD_0LC0LF_---0LA(bbch)1RB0LE_0LC---_1LA0RD_1RC0RC_1LF1LE_0LA1RF(bbch)
Decider
For typical cases, we can fold the tape so that two counters overlap as one counter, and then it's usually decidable by CTL.
Inductive decider can deal with some more complex situations.