1RB3LA1LA1RA1RA 2LB2RA---4RB1LB: Difference between revisions
Jump to navigation
Jump to search
Added link to "Cryptid" |
Added note about decreasing likelihood of halting |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{machine|1RB3LA1LA1RA1RA_2LB2RA---4RB1LB}} | {{machine|1RB3LA1LA1RA1RA_2LB2RA---4RB1LB}} | ||
{{TM|1RB3LA1LA1RA1RA_2LB2RA---4RB1LB}} is a [[BB(2,5)]] TM | {{TM|1RB3LA1LA1RA1RA_2LB2RA---4RB1LB}} is a [[BB(2,5)]] TM analyzed by mxdys [https://discord.com/channels/960643023006490684/1349040227548663858/1349327014955319339 on 12 Mar 2025] that appears to be a [[Cryptid]]. | ||
Analysis by mxdys and Racheline | == Analysis by mxdys and Racheline == | ||
<pre> | <pre> | ||
1RB3LA1LA1RA1RA_2LB2RA---4RB1LB | 1RB3LA1LA1RA1RA_2LB2RA---4RB1LB | ||
| Line 18: | Line 18: | ||
B(a,b) := 0^inf 1 4^a 1^3+b A> 11 0^inf | B(a,b) := 0^inf 1 4^a 1^3+b A> 11 0^inf | ||
</pre> | </pre> | ||
<pre> | |||
Let's rewrite the first rule as: | |||
A(a, b) --> A(2a + 4, b - a - 3) if b >= a + 3 | |||
Then, after n applications of rule 1 (assuming b is large enough): | |||
A(a, b) --> A(2^n * a + 2^(n + 2) - 4, b - 2^n * a + a - 2^(n + 2) + n + 4) | |||
Considering that a is always set to 4 when leaving B, this simplifies to: | |||
A(4, b) --> A(2^(n + 3) - 4, b - 2^(n + 3) + n + 8) | |||
Now consider the halting configuration: A(a, a + 1): | |||
For this to be in a halting configuration, the following must be true: | |||
2^(n+3)-4 + 1 = b-2^(n+3)+n+8 | |||
This simplifies to: | |||
b = 2^(n+4)-n-11 | |||
--> For any positive integer n (and 0): A(4, 2^(n+4)-n-11) --> halt | |||
Considering that all rules either keep the overall score or increase it, and that the transition from B(3a+1,b) moves the score onto b, it is guaranteed that b will always increase between A(4,b) configs. | |||
As a result of this, once a halting value of b is passed, it cannot be reached again. However, as b increases, the distance between these halting values of b increases exponentially, making it less and less likely for the TM to halt. | |||
</pre> | |||
[[Category:BB(2,5)]] | |||
Latest revision as of 21:05, 25 October 2025
1RB3LA1LA1RA1RA_2LB2RA---4RB1LB (bbch) is a BB(2,5) TM analyzed by mxdys on 12 Mar 2025 that appears to be a Cryptid.
Analysis by mxdys and Racheline
1RB3LA1LA1RA1RA_2LB2RA---4RB1LB start: A(4,4) A(a,3+a+b) --> A(4+2a,b) A(a,2+a) --> B(2a+2,3) A(a,1+a) --> halt A(b+a,b) --> B(a,2b) B(3a+1,b) --> A(4,2+5a+b) B(3a+2,b) --> B(5+5a+b,2) B(3a+0,b) --> B(3+5a+b,0) A(a,b) := 0^inf 1 4^a 1^4 A> 1^b 2 0^inf B(a,b) := 0^inf 1 4^a 1^3+b A> 11 0^inf
Let's rewrite the first rule as: A(a, b) --> A(2a + 4, b - a - 3) if b >= a + 3 Then, after n applications of rule 1 (assuming b is large enough): A(a, b) --> A(2^n * a + 2^(n + 2) - 4, b - 2^n * a + a - 2^(n + 2) + n + 4) Considering that a is always set to 4 when leaving B, this simplifies to: A(4, b) --> A(2^(n + 3) - 4, b - 2^(n + 3) + n + 8) Now consider the halting configuration: A(a, a + 1): For this to be in a halting configuration, the following must be true: 2^(n+3)-4 + 1 = b-2^(n+3)+n+8 This simplifies to: b = 2^(n+4)-n-11 --> For any positive integer n (and 0): A(4, 2^(n+4)-n-11) --> halt Considering that all rules either keep the overall score or increase it, and that the transition from B(3a+1,b) moves the score onto b, it is guaranteed that b will always increase between A(4,b) configs. As a result of this, once a halting value of b is passed, it cannot be reached again. However, as b increases, the distance between these halting values of b increases exponentially, making it less and less likely for the TM to halt.