Cycler: Difference between revisions
Jump to navigation
Jump to search
Added information about the decider for cyclers |
other computational models |
||
| Line 5: | Line 5: | ||
'''û''' → '''û''' | '''û''' → '''û''' | ||
where '''û''' is any headed tape segment. | where '''û''' is any headed tape segment. | ||
Most deterministic computational models have cyclers, like lambda calculus, fractran or register machines. | |||
==Related Functions== | ==Related Functions== | ||
Revision as of 21:30, 15 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 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 rule for identifying cyclers is simple:
û → û
where û is any headed tape segment.
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.