Placid Platypus: Difference between revisions
Jump to navigation
Jump to search
elaboration |
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. |
||
| Line 1: | Line 1: | ||
The '''Placid Platypus''' function <math>PP(n)</math> <ref>James Harland. [https://dl.acm.org/doi/pdf/10.5555/1151785.1151794 The Busy Beaver, the Placid Platypus and other Crazy Creatures]. 2006.</ref> is the minimal number of states of 2-symbol Turing machines that print exactly n ones when halt. | The '''Placid Platypus''' function <math>PP(n)</math> <ref>James Harland. [https://dl.acm.org/doi/pdf/10.5555/1151785.1151794 The Busy Beaver, the Placid Platypus and other Crazy Creatures]. 2006.</ref> is the minimal number of states of 2-symbol Turing machines that print exactly n ones when halt. | ||
<math> PP(n) \leq n </math>, because you can print each 1 in a state. Also if <math> n > \Sigma(m)</math>, then <math> PP(n) > m </math>. On the other side, there is also a connection to [[Lazy Beaver]] ( | <math> PP(n) \leq n </math>, because you can print each 1 in a state. Also if <math> n > \Sigma(m)</math>, then <math> PP(n) > m </math>. On the other side, there is also a connection to a variation of the [[Lazy Beaver]] function (determined by ones rather than steps): if <math>n < LB_\Sigma(m)</math> then <math>PP(n) \le m</math>. | ||
Note that this function is not strictly increasing, and that it | Note that this function is not strictly increasing, and that it may be computable. | ||
== Values == | == Values == | ||
Latest revision as of 17:02, 28 September 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)
|
References
- ↑ James Harland. The Busy Beaver, the Placid Platypus and other Crazy Creatures. 2006.