Cycler: Difference between revisions
Used Template:Stub |
Created a section for cycler decider algorithm. |
||
| (3 intermediate revisions by 2 users not shown) | |||
| Line 5: | Line 5: | ||
'''û''' → '''û''' | '''û''' → '''û''' | ||
where '''û''' is any headed tape segment. | where '''û''' is any headed tape segment. | ||
== Decider Algorithm == | |||
The [[decider]] for cyclers works by memorizing all configurations which are visited by a TM. If a configuration is visited twice, the TM is shown to be non-halting. | |||
The algorithm can be optimized by checking a single configuration per step. The saved configuration is saved at a logarithmic tape (e.g. every power of 2 steps). This allows detecting cyclers of any period and preperiod while keeping the time complexity at O(n). | |||
== Other Models == | |||
Most deterministic computational models have cyclers, like lambda calculus, fractran or register machines. | |||
==Related Functions== | |||
* Busy Preperiodic Beaver ([[BBS]](n,m)): The longest possible preperiod of a cycler or translated cycler with n states and m symbols. | |||
* Busy Periodic Beaver ([[BBP]](n,m)): The longest possible period of a cycler or translated cycler with n states and m symbols. | |||
== See also == | == See also == | ||
| Line 11: | Line 24: | ||
* [https://github.com/bbchallenge/bbchallenge-proofs/blob/build-latex-pdf/deciders/correctness-deciders.pdf Section 2] of bbchallenge's deciders write-up. | * [https://github.com/bbchallenge/bbchallenge-proofs/blob/build-latex-pdf/deciders/correctness-deciders.pdf Section 2] of bbchallenge's deciders write-up. | ||
[[Category:Zoology]] | [[Category:Zoology]][[Category:Deciders]] | ||
Latest revision as of 19:21, 27 August 2026
1RB0LB_1LB1LC_0RC1RA (bbch), which has period 18 and preperiod 4.A cycler is a Turing machine that eventually enters a repeating cycle. Such a Turing machine runs forever and thus is a non-halting Turing machine. A cycler may be seen as a special case of a translated cycler which has offset zero.
The rule for identifying cyclers is simple:
û → û
where û is any headed tape segment.
Decider Algorithm
The decider for cyclers works by memorizing all configurations which are visited by a TM. If a configuration is visited twice, the TM is shown to be non-halting.
The algorithm can be optimized by checking a single configuration per step. The saved configuration is saved at a logarithmic tape (e.g. every power of 2 steps). This allows detecting cyclers of any period and preperiod while keeping the time complexity at O(n).
Other Models
Most deterministic computational models have cyclers, like lambda calculus, fractran or register machines.
Related Functions
- Busy Preperiodic Beaver (BBS(n,m)): The longest possible preperiod of a cycler or translated cycler with n states and m symbols.
- Busy Periodic Beaver (BBP(n,m)): The longest possible period of a cycler or translated cycler with n states and m symbols.
See also
- Translated cycler
- Section 2 of bbchallenge's deciders write-up.