Irregular Turing Machine

From BusyBeaverWiki
Revision as of 18:51, 1 October 2026 by Sligocki (talk | contribs) (Add discussion of Domains with irregular TMs)
Jump to navigation Jump to search

A Turing machine is irregular if it cannot be decided using regular CTL, which means there is no regular language, closed under TM step, that includes the initial config and excludes all halting configurations.[1]

Domains with Irregular TMs

All non-halting TMs in domains BB(2), BB(3), BB(4), BB(2,3) and BB(2,4) are regular. This was proven by deciding these domains completely using only regular deciders as described in the BB(5) paper.[2]

BB(5) contains at least two irregular TMs. All BB(5) except for the 13 sporadic TMs are regular. Among the sporadic TMs:

It seems that all Cryptids are irregular, but we are not aware of a written proof for any of them yet. If that is the case, then all domains bigger than BB(6), BB(2,5) and BB(3,3) contain irregular TMs.

Notable examples

References

  1. ↑ https://discord.com/channels/960643023006490684/960643023530762341/1357307689109028874
  2. ↑ Determination of the fifth Busy Beaver value. The bbchallenge Collaboration et al. https://arxiv.org/abs/2509.12337