Placid Platypus: Difference between revisions
Jump to navigation
Jump to search
Comment about LB connection. |
elaboration |
||
| 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]]: if <math>n < LB(m)</math> then <math>PP(n) \le m</math>. | <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]] (or, a variant that is instead determined by ones rather than steps): if <math>n < LB(m)</math> then <math>PP(n) \le m</math>. | ||
Note that this function is not strictly increasing, and that it is computable. | |||
== Values == | == Values == | ||
| Line 7: | Line 9: | ||
!n | !n | ||
!<math>PP(n)</math> | !<math>PP(n)</math> | ||
!TM | !Example TM | ||
|- | |- | ||
|1 | |1 | ||
| Line 24: | Line 26: | ||
|2 | |2 | ||
|{{TM|1RB1LB_1LA1RZ|halt}} | |{{TM|1RB1LB_1LA1RZ|halt}} | ||
|- | |||
|5 | |||
|3 | |||
|{{TM|1RB1RZ_1LB0RC_1LC1LA|halt}} | |||
|- | |||
|6 | |||
|3 | |||
|{{TM|1RB1RZ_0RC1RB_1LC1LA|halt}} | |||
|- | |||
|7 | |||
|4 | |||
|{{TM|1RB1LC_0RC0RB_0LD0LA_1LA1RZ|halt}} | |||
|- | |||
|8 | |||
|4 | |||
|{{TM|1RB1RZ_1LC0RD_1LA1LB_0LC1RD|halt}} | |||
|- | |||
|9 | |||
|4 | |||
|{{TM|1RB1LD_1LC0RB_1RA1LA_1RZ0LC|halt}} | |||
|- | |||
|10 | |||
|4 | |||
|{{TM|1RB1RZ_1LC1RA_0RC0LD_1RD0LB|halt}} | |||
|- | |||
|11 | |||
|4 | |||
|{{TM|1RB1LD_0LC0RC_1LC1LA_1RZ0LA|halt}} | |||
|- | |||
|12 | |||
|4 | |||
|{{TM|1RB0RD_1LC0LA_1RA1LB_1RZ0RC|halt}} | |||
|- | |||
|13 | |||
|4 | |||
|{{TM|1RB1LB_1LA0LC_1RZ1LD_1RD0RA|halt}} | |||
|- | |||
|14 | |||
|5 | |||
|{{TM|1RB0LB_0LC1RZ_1LE0RD_1RC0RA_1LD0LB|halt}} | |||
|- | |||
|15 | |||
|5 | |||
|{{TM|1RB0LD_1LC0LB_1RD0RC_1LA0RE_1RA1RZ|halt}} | |||
|} | |} | ||
== References == | == References == | ||
<references /> | <references /> | ||
[[Category:Functions]] | [[Category:Functions]] | ||
Revision as of 16:53, 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 Lazy Beaver (or, a variant that is instead determined by ones rather than steps): if then .
Note that this function is not strictly increasing, and that it is 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.