User:MrSolis/Playground: Difference between revisions

From BusyBeaverWiki
Jump to navigation Jump to search
VisualWikitext
No edit summary
(Blanked the page)
Tags: Blanking Manual revert
 
Line 1: Line 1:
{{unsolved|Does Antihydra run forever?}}{{TM|1RB1RA_0LC1LE_1LD1LC_1LA0LB_1LF1RE_---0RA|undecided}}
[[File:Antihydra-depiction.png|right|thumb|Artistic depiction of Antihydra by Jadeix]]
'''ANTIHYDRA PAGE REVAMP (WIP)'''


'''Antihydra''' is a [[BB(6)]] [[Cryptid]]. It is similar to [[Hydra]] in that it halts if and only if the sequence
<math display="block">H_{n+1}=\bigg\lfloor\frac{3}{2}H_n\bigg\rfloor,H_0=8,</math>
ever has more than twice the number of odd terms as the amount of even terms.
== Analysis ==
===Rules===
Let <math>A(a,b):=0^\infty\;1^a\;0\;1^b\;\textrm{E>}\;0^\infty</math>. Then<ref name="bl">S. Ligocki, "[https://www.sligocki.com/2024/07/06/bb-6-2-is-hard.html BB(6) is Hard (Antihydra)]" (2024). Accessed 22 July 2024.</ref>,
<math display="block">\begin{array}{|lll|}\hline
A(a,2b)& \xrightarrow{2a+3b^2+12b+11}& A(a+2,3b+2),\\
A(0,2b+1)&\xrightarrow{3b^2+9b-1}& 0^\infty\;\textrm{<F}\;110\;1^{3b}\;0^\infty,\\
A(a+1,2b+1)&\xrightarrow{3b^2+12b+5}& A(a,3b+3).\\\hline
\end{array}</math>
===Proof===
Consider the partial configuration <math>P(m,n):=0\;1^m\;\textrm{E>}\;0\;1^n\;0^\infty</math>. The configuration after two steps is <math>0\;1^{m-1}\;0\;\textrm{A>}\;1^{n+1}\;0^\infty</math>. We note the following shift rule:
<math display="block">\begin{array}{|c|}\hline\textrm{A>}\;1^s\xrightarrow{s}1^s\;\textrm{A>}\\\hline\end{array}</math>
As a result, we get <math>0\;1^{m-1}\;0\;1^{n+1}\;\textrm{A>}\;0^\infty</math> after <math>n+1</math> steps. Advancing two steps produces <math>0\;1^{m-1}\;0\;1^{n+2}\;\textrm{<C}\;0^\infty</math>. A second shift rule is useful here:
<math display="block">\begin{array}{|c|}\hline1^s\;\textrm{<C}\xrightarrow{s}\textrm{<C}\;1^s\\\hline\end{array}</math>
This allows us to reach <math>0\;1^{m-1}\;0\;\textrm{<C}\;1^{n+2}\;0^\infty</math> in <math>n+2</math> steps. Moving five more steps gets us to <math>0\;1^{m-2}\;\textrm{E>}\;0\;1^{n+3}\;0^\infty</math>, which is the same configuration as <math>P(m-2,n+3)</math>. Accounting for the head movement creates the condition that <math>m\ge 4</math>. In summary:
<math display="block">\begin{array}{|c|}\hline P(m,n)\xrightarrow{2n+12}P(m-2,n+3)\text{ if }m\ge 4.\\\hline\end{array}</math>
With <math>A(a,b)</math> we have <math>P(b,0)</math>. As a result, we can apply this rule <math display="inline>\big\lfloor\frac{1}{2}b\big\rfloor-1</math> times (assuming <math>b\ge 4</math>), which creates two possible scenarios:
#If <math>b\equiv0\ (\operatorname{mod}2)</math>, then in <math>\sum_{i=0}^{(b/2)-2}(2\times 3i+12)=\textstyle\frac{3}{4}b^2+\frac{3}{2}b-6</math> steps we arrive at <math display="inline">P\Big(2,\frac{3}{2}b-3\Big)</math>. The matching complete configuration is <math>0^\infty\;1^a\;011\;\textrm{E>}\;0\;1^{(3b)/2-3}\;0^\infty</math>. After <math>3b+4</math> steps this becomes <math>0^\infty\;1^a\;\textrm{<C}\;00\;1^{(3b)/2}\;0^\infty</math>, which then leads to <math>0^\infty\;\textrm{<C}\;1^a\;00\;1^{(3b)/2}\;0^\infty</math> in <math>a</math> steps. After five more steps, we reach <math>0^\infty\;1\;\textrm{E>}\;1^{a+2}\;00\;1^{(3b)/2}\;0^\infty</math>, from which another shift rule must be applied:<math display="block">\begin{array}{|c|}\hline\textrm{E>}\;1^s\xrightarrow{s}1^s\;\textrm{E>}\\\hline\end{array}</math>Doing so allows us to get the configuration <math>0^\infty\;1^{a+3}\;\textrm{E>}\;00\;1^{(3b)/2}\;0^\infty</math> in <math>a+2</math> steps. In six steps we have <math>0^\infty\;1^{a+2}\;011\;\textrm{E>}\;1^{(3b)/2}\;0^\infty</math>, so we use the shift rule again, ending at <math>0^\infty\;1^{a+2}\;0\;1^{(3b)/2+2}\;\textrm{E>}\;0^\infty</math>, equal to <math display="inline">A\Big(a+2,\frac{3}{2}b+2\Big)</math>, <math display="inline">\frac{3}{2}b</math> steps later. This gives a total of <math display="inline">2a+\frac{3}{4}b^2+6b+11</math> steps.
#If <math>b\equiv1\ (\operatorname{mod}2)</math>, then in <math display="inline">\frac{3}{4}b^2-\frac{27}{4}</math> steps we arrive at <math display="inline">P\Big(3,\frac{3b-9}{2}\Big)</math>. The matching complete configuration is <math>0^\infty\;1^a\;0111\;\textrm{E>}\;0\;1^{(3b-9)/2}\;0^\infty</math>. After <math>3b+2</math> steps this becomes <math>0^\infty\;1^a\;\textrm{<F}\;110\;1^{(3b-3)/2}\;0^\infty</math>. If <math>a=0</math> then we have reached the undefined <code>F0</code> transition with a total of <math display="inline">\frac{3}{4}b^2+3b-\frac{19}{4}</math> steps. Otherwise, continuing for six steps gives us <math>0^\infty\;1^{a-1}\;0111\;\textrm{E>}\;1^{(3b-3)/2}\;0^\infty</math>. We conclude with the configuration <math>0^\infty\;1^{a-1}\;0\;1^{(3b+3)/2}\;\textrm{E>}\;0^\infty</math>, equal to <math display="inline">A\Big(a-1,\frac{3b+3}{2}\Big)</math>, in <math display="inline">\frac{3b-3}{2}</math> steps. This gives a total of <math display="inline">\frac{3}{4}b^2+\frac{9}{2}b-\frac{1}{4}</math> steps.
The information above can be summarized as
<math display="block">A(a,b)\rightarrow\begin{cases}A\Big(a+2,\frac{3}{2}b+2\Big)&\text{if }b\ge 2,b\equiv0\pmod{2};\\0^\infty\;\textrm{<F}\;110\;1^{(3b-3)/2}\;0^\infty&\text{if }b\ge3,b\equiv1\pmod{2},\text{ and }a=0;\\A\Big(a-1,\frac{3b+3}{2}\Big)&\text{if }b\ge3,b\equiv1\pmod{2},\text{ and }a>0.\end{cases}</math>
Substituting <math>b\leftarrow 2b</math> for the first case and <math>b\leftarrow 2b+1</math> for the other two yields the final result.
== Trajectory ==
11 steps are required to enter the configuration <math>A(0, 4)</math> before the [[Collatz-like]] rules are repeatedly applied. Here are the first few iterations:
<math display="block">\begin{array}{|c|}\hline A(0,4)\xrightarrow{47}A(2,8)\xrightarrow{111}A(4,14)\xrightarrow{250}A(6,23)\xrightarrow{500}A(5,36)\xrightarrow{1209}A(7,56)\rightarrow\cdots\\\hline\end{array}</math>
The halting problems for Antihydra and Hydra are connected by the [[Hydra function]], so the heuristic argument suggesting that machine is [[probviously]] nonhalting can be applied here. After <math>2^{31}</math> rule steps, we have <math>b=1073720884</math><ref name="bl"></ref>, so this machine, if treated as a random process, has an extremely minuscule chance of ever halting.
==References==

Latest revision as of 00:57, 17 February 2025

Retrieved from "https://wiki.bbchallenge.org/w/index.php?title=User:MrSolis/Playground&oldid=1564"