Placid Platypus: Difference between revisions
Jump to navigation
Jump to search
Good point about the Sigma vs S issue, sigh. This also makes it unclear to me if it is computable. I think the S version would be, but not the Sigma version. |
Loader3229 (talk | contribs) |
||
| Line 70: | Line 70: | ||
|5 | |5 | ||
|{{TM|1RB0LD_1LC0LB_1RD0RC_1LA0RE_1RA1RZ|halt}} | |{{TM|1RB0LD_1LC0LB_1RD0RC_1LA0RE_1RA1RZ|halt}} | ||
|- | |||
|16 | |||
|5 | |||
|{{TM|1RB1RE_1RC1RZ_0LD0RA_1RA1LD_1RD0LE|halt}} | |||
|- | |||
|17 | |||
|5 | |||
|{{TM|1RB1RE_1RC0RZ_1LD1LC_0LB1RA_1LC1RD|halt}} | |||
|- | |||
|18 | |||
|5 | |||
|{{TM|1RB1RE_1RC1RZ_1LD1LC_0LB1RA_1LC1RD|halt}} | |||
|- | |||
|19 | |||
|5 | |||
|{{TM|1RB1RE_1RC1RZ_1LE0RA_0LE1RC_0RA0LD|halt}} | |||
|- | |||
|20 | |||
|5 | |||
|{{TM|1RB0RZ_1RC1RE_1LD0RE_0LE0LD_1LB1RA|halt}} | |||
|- | |||
|21 | |||
|5 | |||
|{{TM|1RB1RZ_1RC1RE_1LD0RE_0LE0LD_1LB1RA|halt}} | |||
|- | |||
|22 | |||
|5 | |||
|{{TM|1RB1RZ_1RC1RE_1LD0RB_0LE1LC_1RA0LC|halt}} | |||
|} | |} | ||
== References == | == References == | ||
<references /> | <references /> | ||
[[Category:Functions]] | [[Category:Functions]] | ||
Revision as of 01:40, 5 October 2026
The Placid Platypus function [1] is the minimal number of states of 2-symbol Turing machines that print exactly n ones when halt.
, because you can print each 1 in a state. Also if , then . On the other side, there is also a connection to a variation of the Lazy Beaver function (determined by ones rather than steps): if then .
Note that this function is not strictly increasing, and that it may be computable.
Values
| n | Example TM | |
|---|---|---|
| 1 | 1 | 1RZ--- (bbch)
|
| 2 | 2 | 1RB---_1RZ--- (bbch)
|
| 3 | 2 | 1RB1LA_1LA1RZ (bbch)
|
| 4 | 2 | 1RB1LB_1LA1RZ (bbch)
|
| 5 | 3 | 1RB1RZ_1LB0RC_1LC1LA (bbch)
|
| 6 | 3 | 1RB1RZ_0RC1RB_1LC1LA (bbch)
|
| 7 | 4 | 1RB1LC_0RC0RB_0LD0LA_1LA1RZ (bbch)
|
| 8 | 4 | 1RB1RZ_1LC0RD_1LA1LB_0LC1RD (bbch)
|
| 9 | 4 | 1RB1LD_1LC0RB_1RA1LA_1RZ0LC (bbch)
|
| 10 | 4 | 1RB1RZ_1LC1RA_0RC0LD_1RD0LB (bbch)
|
| 11 | 4 | 1RB1LD_0LC0RC_1LC1LA_1RZ0LA (bbch)
|
| 12 | 4 | 1RB0RD_1LC0LA_1RA1LB_1RZ0RC (bbch)
|
| 13 | 4 | 1RB1LB_1LA0LC_1RZ1LD_1RD0RA (bbch)
|
| 14 | 5 | 1RB0LB_0LC1RZ_1LE0RD_1RC0RA_1LD0LB (bbch)
|
| 15 | 5 | 1RB0LD_1LC0LB_1RD0RC_1LA0RE_1RA1RZ (bbch)
|
| 16 | 5 | 1RB1RE_1RC1RZ_0LD0RA_1RA1LD_1RD0LE (bbch)
|
| 17 | 5 | 1RB1RE_1RC0RZ_1LD1LC_0LB1RA_1LC1RD (bbch)
|
| 18 | 5 | 1RB1RE_1RC1RZ_1LD1LC_0LB1RA_1LC1RD (bbch)
|
| 19 | 5 | 1RB1RE_1RC1RZ_1LE0RA_0LE1RC_0RA0LD (bbch)
|
| 20 | 5 | 1RB0RZ_1RC1RE_1LD0RE_0LE0LD_1LB1RA (bbch)
|
| 21 | 5 | 1RB1RZ_1RC1RE_1LD0RE_0LE0LD_1LB1RA (bbch)
|
| 22 | 5 | 1RB1RZ_1RC1RE_1LD0RB_0LE1LC_1RA0LC (bbch)
|
References
- ↑ James Harland. The Busy Beaver, the Placid Platypus and other Crazy Creatures. 2006.