Irregular Turing Machine: Difference between revisions
Jump to navigation
Jump to search
Referencing |
Clarify definition |
||
| Line 1: | Line 1: | ||
{{Stub}} | {{Stub}} | ||
A [[Turing machine]] is irregular if it cannot be decided using regular [[CTL]], which means there is no regular language, closed under TM | 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> | ||
== Notable examples == | == Notable examples == | ||
Latest revision as of 18:31, 21 September 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]
Notable examples
1RB1RE_1LC1RB_0RA0LD_1LB1LD_---0RA(bbch), also called Finned #3.1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA(bbch), also called Skelet 17.