Placid Platypus: Difference between revisions
Jump to navigation
Jump to search
Loader3229 (talk | contribs) No edit summary |
Comment about LB connection. |
||
| 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>. | <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>. | ||
== Values == | == Values == | ||
Revision as of 16:08, 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: if then .
Values
| n | TM | |
|---|---|---|
| 1 | 1 | 1RZ--- (bbch)
|
| 2 | 2 | 1RB---_1RZ--- (bbch)
|
| 3 | 2 | 1RB1LA_1LA1RZ (bbch)
|
| 4 | 2 | 1RB1LB_1LA1RZ (bbch)
|
References
- ↑ James Harland. The Busy Beaver, the Placid Platypus and other Crazy Creatures. 2006.