1RB3RB---3LA1RA 2LA3RA4LB0LB1LB: Difference between revisions
(Added description of how it becomes a biased random walker and looks exactly like one for the first 100M steps.) |
(Cleanup text) |
||
| Line 1: | Line 1: | ||
{{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB1LB|undecided}} sometimes called "Bonus Cryptid" is a [[BB(2,5)]] found by Daniel Yuan in May 2024. It | {{TM|1RB3RB---3LA1RA_2LA3RA4LB0LB1LB|undecided}} sometimes called "Bonus Cryptid" is a [[BB(2,5)]] Pseudo-random walking [[Cryptid]] found by Daniel Yuan in May 2024. It has been simulated out to 100 million rule steps. | ||
See https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html#a-bonus-cryptid | See https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html#a-bonus-cryptid | ||
| Line 19: | Line 17: | ||
A(3n+2, b+1) -> A(4n+5, b) | A(3n+2, b+1) -> A(4n+5, b) | ||
Start: A(1287547464911049659, 10) | |||
</ | </pre>Note: This TM enters an "A()" config much earlier: <code>A(3, 1)</code> but then reaches the undefined <code>A(3n+2, 0)</code> rule several times before reaching the start config listed above. | ||
In Feb 2025, Racheline [https://discord.com/channels/960643023006490684/1259770421046411285/1337181169233559633 simulated] it past the unknown rule. According to her simulation, the machine reaches <code>A(1287547464911049659,10)</code> after <code>1894603970741566467769886232237213051</code> steps, and from there, the TM seems to be a cryptid. Andrew simulated it 100 million (rule) steps beyond this intermediate point, finding <code>b=33320662</code>and "a" on the order of 10^12493892. This matches exactly what we would expect to see from a biased random walk biased towards traveling away from the origin with probability two-thirds. Note the halting condition requires b = 0, which we are probviously unlikely to ever reach again, but if the TM did make it back, there is no guarantee the machine halts. It could simply spiral back into either the a = 3n+1 or a = 3n+2 cases and return to its random walk condition again. | |||
== Analysis by Andrew Ducharme == | == Analysis by Andrew Ducharme == | ||
Revision as of 20:36, 11 February 2025
1RB3RB---3LA1RA_2LA3RA4LB0LB1LB (bbch) sometimes called "Bonus Cryptid" is a BB(2,5) Pseudo-random walking Cryptid found by Daniel Yuan in May 2024. It has been simulated out to 100 million rule steps.
See https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html#a-bonus-cryptid
Behavior
1RB3RB---3LA1RA_2LA3RA4LB0LB1LB Define A(a, b) = 0^inf <B 0^a 3^b 2 0^inf The rules are A(3n, 0) -> Halt A(3n, b+1) -> A(4n+3, b) A(3n+1, b) -> A(4n+3, b+3) A(3n+2, 0) -> ? A(3n+2, b+1) -> A(4n+5, b) Start: A(1287547464911049659, 10)
Note: This TM enters an "A()" config much earlier: A(3, 1) but then reaches the undefined A(3n+2, 0) rule several times before reaching the start config listed above.
In Feb 2025, Racheline simulated it past the unknown rule. According to her simulation, the machine reaches A(1287547464911049659,10) after 1894603970741566467769886232237213051 steps, and from there, the TM seems to be a cryptid. Andrew simulated it 100 million (rule) steps beyond this intermediate point, finding b=33320662and "a" on the order of 10^12493892. This matches exactly what we would expect to see from a biased random walk biased towards traveling away from the origin with probability two-thirds. Note the halting condition requires b = 0, which we are probviously unlikely to ever reach again, but if the TM did make it back, there is no guarantee the machine halts. It could simply spiral back into either the a = 3n+1 or a = 3n+2 cases and return to its random walk condition again.
Analysis by Andrew Ducharme
https://discord.com/channels/960643023006490684/1259770421046411285/1336973758182981634I found in August that it hits A(3n+2,0) after 113 A rule steps, but never seriously looked into what happened from there. The tape of the actual TM at that point is ginormous, so I looked at cases A(3n+2,0) -> 0<A 2 0^(3n+2) 2 0. From observations of the cases n=[0,1,2,...,10], the tape A(3n+2, 0) goes to (16/3 n + 7 , 1) if n = 0 (mod 3), (16/3n + 25/3, 2) if n = 2 (mod 3). God knows what happens if n is congruent to 1. Using these rules, I was able to go from 113 rule steps to........118 before the congruent 1 case was triggered.
In the first two cases, the lone 2 on the right hand side of the tape becomes a lone 4, and then is subsumed into the normal A(a,b) framework. In the last case, the lone 2 becomes a lone 4, then becomes a lone 1, but from there, I don't see a pattern. Sometimes it fixes itself, like when n = 1, but sometimes we enter a whole new phase like with n = 4.