Placid Platypus
The Placid Platypus function PP[1] is the minimal number of states of 2-symbol Turing machines that print exactly n ones when halt.
PP(n) ≤ n, because you can print each 1 in a state. Also if n > Σ(m), then PP(n) > m. On the other side, there is also a connection to a variation of the Lazy Beaver function, where LBΣ(m) = n iff no m-state machine print exactly n ones and the same is false for all smaller values: if n ≤ LBΣ(m) then PP(n) ≤ m.
Note that this function is not strictly increasing.
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_1RC1RB_1RE0RA_1LA0LE_1LD0RC (bbch)
|
| 23 | 5 | 1RB0LD_1RC0RB_1LA0RA_0LC0LE_1LC1RZ (bbch)
|
| 24 | 5 | 1RB1RD_1RC0RE_1LE1RZ_1LD0LE_1RA0LA (bbch)
|
| 25 | 5 | 1RB1RD_0RC0RZ_1LC1LD_1RE0LC_1RA0RE (bbch)
|
| 26 | 5 | 1RB1RD_0RC1RZ_1LC1LD_1RE0LC_1RA0RE (bbch)
|
| 27 | 5 | 1RB1RZ_1RC1RB_1RD1RA_1LE0RC_1LC0LD (bbch)
|
| 28 | 5 | 1RB1RZ_0RC0RD_1RD1LE_1RE1RB_1LC1LA (bbch)
|
| 29 | 5 | 1RB0RZ_1RC0RE_1RD0LE_1RE0RA_1LC0LE (bbch)
|
| 30 | 5 | 1RB1RZ_1RC0RE_1RD0LE_1RE0RA_1LC0LE (bbch)
|
| 31 | 5 | 1RB1RE_1RC1RD_1LD0LC_1RA0LC_0RD0RZ (bbch)
|
| 32 | 5 | 1RB1RE_1RC1RD_1LD0LC_1RA0LC_0RD1RZ (bbch)
|
| 33 | 5 | 1RB---_1RC1RD_1LD0RB_0RE0LC_0RZ1RA (bbch)
|
| 34 | 5 | 1RB---_1RC1RD_1LD0RB_0RE0LC_1RZ1RA (bbch)
|
| 35 | 5 | 1RB1RZ_1RC1RD_1LD0RB_0RE0LC_1LE1RA (bbch)
|
| 36 | 5 | 1RB1RE_1RC1RB_1LD0RA_1LB1LD_0RZ1RC (bbch)
|
| 37 | 5 | 1RB1RE_1RC1RB_1LD0RA_1LB1LD_1RZ1RC (bbch)
|
References
- ↑ James Harland. The Busy Beaver, the Placid Platypus and other Crazy Creatures. 2006.