Irregular Turing Machine: Difference between revisions
Clarify definition |
Add definition directly to this page |
||
| (4 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
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.<ref>https://discord.com/channels/960643023006490684/960643023530762341/1357307689109028874</ref> | 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.<ref>https://discord.com/channels/960643023006490684/960643023530762341/1357307689109028874</ref> | ||
== Definition == | |||
A TM is '''regular''' if there exists a set C of TM configs defined a [[wikipedia:Regular_language|regular language]] such that: | |||
# Init config is in C | |||
# C is closed under TM step: forall configs c in C and c -> d (config after 1 TM step) then d in C | |||
# C does not contain any halting configs | |||
Proving the existence of such a set is sufficient to prove the TM is non-halting. Most existing [[deciders]] can only prove regular TMs non-halting (Ex: [[CTL]], [[FAR]], [[CPS]], [[RepWL]]). Any non-halting TM which is not regular is called '''irregular'''. | |||
== 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.<ref>'''Determination of the fifth Busy Beaver value.''' The bbchallenge Collaboration et al. https://arxiv.org/abs/2509.12337</ref> | |||
[[BB(5)]] contains at least two irregular TMs. All BB(5) TMs except for the 30 (13 [[sporadic TMs]] and 17 proven by [[WFAR]]) are known regular. Among these remaining 30 TMs: | |||
* 1 Proven Regular: [[Skelet 1]] | |||
* 2 Proven Irregular: [[Finned 3]] by Iijil in 2023<ref>"10756090 (Finned #3) is irregular". 17 Mar 2023. By Iijil.https://discuss.bbchallenge.org/t/10756090-finned-3-is-irregular/137</ref> and [[Skelet 17]] by Daniel Yuan in 2024<ref>https://discord.com/channels/960643023006490684/1082035052961091705/1269022847502647357</ref> (see [[Skelet 17#Irregularity]]) | |||
* 27 Unknown regularity: [[Skelet 10]], 5 [[Shift overflow counter|Shift overflow counters]], other 4 finned TMs, and 17 proven by WFAR. According to Justin Blanchard, all of these are suspected of being irregular.<ref>https://discord.com/channels/960643023006490684/1295401870298320977/1337815008347951126</ref> | |||
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 == | == Notable examples == | ||
Latest revision as of 19:23, 1 October 2026
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]
Definition
A TM is regular if there exists a set C of TM configs defined a regular language such that:
- Init config is in C
- C is closed under TM step: forall configs c in C and c -> d (config after 1 TM step) then d in C
- C does not contain any halting configs
Proving the existence of such a set is sufficient to prove the TM is non-halting. Most existing deciders can only prove regular TMs non-halting (Ex: CTL, FAR, CPS, RepWL). Any non-halting TM which is not regular is called irregular.
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) TMs except for the 30 (13 sporadic TMs and 17 proven by WFAR) are known regular. Among these remaining 30 TMs:
- 1 Proven Regular: Skelet 1
- 2 Proven Irregular: Finned 3 by Iijil in 2023[3] and Skelet 17 by Daniel Yuan in 2024[4] (see Skelet 17#Irregularity)
- 27 Unknown regularity: Skelet 10, 5 Shift overflow counters, other 4 finned TMs, and 17 proven by WFAR. According to Justin Blanchard, all of these are suspected of being irregular.[5]
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
1RB1RE_1LC1RB_0RA0LD_1LB1LD_---0RA(bbch), also called Finned #3.1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA(bbch), also called Skelet 17.
References
- ↑ https://discord.com/channels/960643023006490684/960643023530762341/1357307689109028874
- ↑ Determination of the fifth Busy Beaver value. The bbchallenge Collaboration et al. https://arxiv.org/abs/2509.12337
- ↑ "10756090 (Finned #3) is irregular". 17 Mar 2023. By Iijil.https://discuss.bbchallenge.org/t/10756090-finned-3-is-irregular/137
- ↑ https://discord.com/channels/960643023006490684/1082035052961091705/1269022847502647357
- ↑ https://discord.com/channels/960643023006490684/1295401870298320977/1337815008347951126