Placid Platypus: Difference between revisions
Jump to navigation
Jump to search
mNo edit summary |
mNo edit summary |
||
| Line 1: | Line 1: | ||
The '''Placid Platypus''' function PP<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 PP<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. | ||
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 | 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<sub>Σ</sub>(m) = n iff no m-state machine print exactly n ones and the same is false for all smaller values: if n ≤ LB<sub>Σ</sub>(m) then PP(n) ≤ m. | ||
Note that this function is not strictly increasing. | Note that this function is not strictly increasing. | ||
Revision as of 04:22, 5 October 2026
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)
|
References
- ↑ James Harland. The Busy Beaver, the Placid Platypus and other Crazy Creatures. 2006.