Sync bi-counter: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
Polygon (talk | contribs)
Used Template:Stub
A6P457 (talk | contribs)
Added 4 state example and non-halting
 
(One intermediate revision by one other user not shown)
Line 7: Line 7:
== Examples ==
== Examples ==


* [https://bbchallenge.org/1RB0RA_0LC1RA_1RE1LD_1LC0LD_---0RB Skelet #10] ([https://www.sligocki.com/2023/03/14/skelet-10.html Proof of non-halt])
* {{TM|1RB1LA_0RC0RB_1LD1RC_0LA0LD|non_halt}}
* {{TM|1RB1LA_1LA0RC_1RB0RD_1LE1RD_0LC0LF_---0LA}}
* {{TM|1LC0LA_---0LC_0RD1LA_1LB1RE_1RD0RE|non_halt}} (Skelet 10) ([https://www.sligocki.com/2023/03/14/skelet-10.html Proof of non-halt])
* {{TM|1RB0LE_0LC---_1LA0RD_1RC0RC_1LF1LE_0LA1RF}}
* {{TM|1RB1LA_1LA0RC_1RB0RD_1LE1RD_0LC0LF_---0LA|non_halt}}
* {{TM|1RB0LE_0LC---_1LA0RD_1RC0RC_1LF1LE_0LA1RF|non_halt}}


== Decider ==
== Decider ==

Latest revision as of 15:39, 3 November 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

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.