Irregular Turing Machine: Difference between revisions
Jump to navigation
Jump to search
Expanded (text taken from https://discord.com/channels/960643023006490684/960643023530762341/1357307689109028874) |
Clarify definition |
||
| (One intermediate revision by one other user not shown) | |||
| 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 == | |||
* {{TM|1RB1RE_1LC1RB_0RA0LD_1LB1LD_---0RA}}, also called Finned #3. | * {{TM|1RB1RE_1LC1RB_0RA0LD_1LB1LD_---0RA}}, also called Finned #3. | ||
* {{TM|1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA}}, also called Skelet 17. | * {{TM|1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA}}, also called Skelet 17. | ||
== References == | |||
[[Category:Zoology]] | [[Category:Zoology]] | ||
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.