Irregular Turing Machine: Difference between revisions
Jump to navigation
Jump to search
Expanded (text taken from https://discord.com/channels/960643023006490684/960643023530762341/1357307689109028874) |
Referencing |
||
| 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 operations, that approximates the language of the machine and does not include any halting configuration. | A [[Turing machine]] is irregular if it cannot be decided using regular [[CTL]], which means there is no regular language, closed under TM operations, that approximates the language of the machine and does not include any halting configuration.<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 13:16, 21 February 2026
A Turing machine is irregular if it cannot be decided using regular CTL, which means there is no regular language, closed under TM operations, that approximates the language of the machine and does not include any halting configuration.[1]
Notable examples
1RB1RE_1LC1RB_0RA0LD_1LB1LD_---0RA(bbch), also called Finned #3.1RB---_0LC1RE_0LD1LC_1RA1LB_0RB0RA(bbch), also called Skelet 17.