Hydra - Revision history

Sligocki: use doi tempate

2025-12-02T16:20:05Z

use doi tempate

← Older revision		Revision as of 16:20, 2 December 2025
Line 2:		Line 2:
	{{TM\|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA\|undecided}}, called '''Hydra''', is a [[BB(2,5)]] [[Cryptid]]. Its high-level rules were first reported [https://discord.com/channels/960643023006490684/1084047886494470185/1231110668288135208 on Discord] by Daniel Yuan on 20 April 2024, who also gave Hydra said name. Later on, a 6-state, 2-symbol [[Turing machine]] was discovered and named [[Antihydra]] for having similar behaviour to Hydra, making the study of this machine important to the study of that one.		{{TM\|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA\|undecided}}, called '''Hydra''', is a [[BB(2,5)]] [[Cryptid]]. Its high-level rules were first reported [https://discord.com/channels/960643023006490684/1084047886494470185/1231110668288135208 on Discord] by Daniel Yuan on 20 April 2024, who also gave Hydra said name. Later on, a 6-state, 2-symbol [[Turing machine]] was discovered and named [[Antihydra]] for having similar behaviour to Hydra, making the study of this machine important to the study of that one.

	Hydra is known to not generate Sturmian words<ref>Dubickas A. On Integer Sequences Generated by Linear Maps. ''Glasgow Mathematical Journal''. 2009; 51(2): 243-252. doi~~:[https://doi.org/10.1017/S0017089508004655~~ 10.1017/S0017089508004655]</ref> (Corollary 4).		Hydra is known to not generate Sturmian words<ref>Dubickas A. On Integer Sequences Generated by Linear Maps. ''Glasgow Mathematical Journal''. 2009; 51(2): 243-252. {{doi\|10.1017/S0017089508004655}}</ref> (Corollary 4).
	<div style="width: fit-content; text-align: center; margin-left: auto; margin-right: auto;">		<div style="width: fit-content; text-align: center; margin-left: auto; margin-right: auto;">
	{\|class="wikitable" style="margin-left: auto; margin-right: auto;"		{\|class="wikitable" style="margin-left: auto; margin-right: auto;"

MrSolis: :(

2025-10-07T22:14:02Z

Hipparcos: fix some directed heads

2025-10-07T16:46:03Z

fix some directed heads

Polygon: Added Category:BB(2,5)

2025-09-27T16:09:43Z

Added Category:BB(2,5)

← Older revision		Revision as of 16:09, 27 September 2025
Line 95:		Line 95:

	==References==		==References==
	[[Category:Cryptids]]		[[Category:BB(2,5)]][[Category:Cryptids]]

Polygon: Combined introduction with link to bbch

2025-08-10T21:25:06Z

Combined introduction with link to bbch

← Older revision		Revision as of 21:25, 10 August 2025
Line 1:		Line 1:
	{{machine\|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA}}{{unsolved\|Does Hydra run forever?}}{{TM\|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA\|undecided}}		{{machine\|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA}}{{unsolved\|Does Hydra run forever?}}
	'''Hydra''' is a [[BB(2,5)]] [[Cryptid]]. Its high-level rules were first reported [https://discord.com/channels/960643023006490684/1084047886494470185/1231110668288135208 on Discord] by Daniel Yuan on 20 April 2024, who also gave Hydra said name. Later on, a 6-state, 2-symbol [[Turing machine]] was discovered and named [[Antihydra]] for having similar behaviour to Hydra, making the study of this machine important to the study of that one.		{{TM\|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA\|undecided}}, called '''Hydra''', is a [[BB(2,5)]] [[Cryptid]]. Its high-level rules were first reported [https://discord.com/channels/960643023006490684/1084047886494470185/1231110668288135208 on Discord] by Daniel Yuan on 20 April 2024, who also gave Hydra said name. Later on, a 6-state, 2-symbol [[Turing machine]] was discovered and named [[Antihydra]] for having similar behaviour to Hydra, making the study of this machine important to the study of that one.

	Hydra is known to not generate Sturmian words<ref>Dubickas A. On Integer Sequences Generated by Linear Maps. ''Glasgow Mathematical Journal''. 2009; 51(2): 243-252. doi:[https://doi.org/10.1017/S0017089508004655 10.1017/S0017089508004655]</ref> (Corollary 4).		Hydra is known to not generate Sturmian words<ref>Dubickas A. On Integer Sequences Generated by Linear Maps. ''Glasgow Mathematical Journal''. 2009; 51(2): 243-252. doi:[https://doi.org/10.1017/S0017089508004655 10.1017/S0017089508004655]</ref> (Corollary 4).

Cosmo: Fast Hydra sim

2025-07-03T10:42:00Z

Fast Hydra sim

@@ Line 52: / Line 52: @@
 <math display="block">\begin{array}{|c|}\hline C(3,0)\xrightarrow{55}C(6,2)\xrightarrow{133}C(12,1)\xrightarrow{364}C(21,0)\xrightarrow{856}C(33,2)\xrightarrow{1938}C(51,4)\xrightarrow{4367}C(78,6)\rightarrow\cdots\\\hline\end{array}</math>
 The heuristic argument that suggests Antihydra is a [[probviously]] non-halting machine can be applied here. This means that if <math>b</math> is to be thought of as moving randomly, then the probability of Hydra halting is <math display="inline">{\Big(\frac{\sqrt{5}-1}{2}\Big)}^{2005374}\approx 4.168\times 10^{-419099}</math>.
 ==References==
 [[Category:Cryptids]]

Sligocki: Capitalization

2025-05-28T18:03:50Z

Capitalization

← Older revision		Revision as of 18:03, 28 May 2025
Line 2:		Line 2:
	'''Hydra''' is a [[BB(2,5)]] [[Cryptid]]. Its high-level rules were first reported [https://discord.com/channels/960643023006490684/1084047886494470185/1231110668288135208 on Discord] by Daniel Yuan on 20 April 2024, who also gave Hydra said name. Later on, a 6-state, 2-symbol [[Turing machine]] was discovered and named [[Antihydra]] for having similar behaviour to Hydra, making the study of this machine important to the study of that one.		'''Hydra''' is a [[BB(2,5)]] [[Cryptid]]. Its high-level rules were first reported [https://discord.com/channels/960643023006490684/1084047886494470185/1231110668288135208 on Discord] by Daniel Yuan on 20 April 2024, who also gave Hydra said name. Later on, a 6-state, 2-symbol [[Turing machine]] was discovered and named [[Antihydra]] for having similar behaviour to Hydra, making the study of this machine important to the study of that one.

	Hydra is known to not generate Sturmian words<ref>~~DUBICKAS~~ A. ~~ON INTEGER SEQUENCES GENERATED BY LINEAR MAPS~~. ''Glasgow Mathematical Journal''. 2009;51(2):243-252. doi:[https://doi.org/10.1017/S0017089508004655 10.1017/S0017089508004655]</ref> (Corollary 4).		Hydra is known to not generate Sturmian words<ref>Dubickas A. On Integer Sequences Generated by Linear Maps. ''Glasgow Mathematical Journal''. 2009; 51(2): 243-252. doi:[https://doi.org/10.1017/S0017089508004655 10.1017/S0017089508004655]</ref> (Corollary 4).
	<div style="width: fit-content; text-align: center; margin-left: auto; margin-right: auto;">		<div style="width: fit-content; text-align: center; margin-left: auto; margin-right: auto;">
	{\|class="wikitable" style="margin-left: auto; margin-right: auto;"		{\|class="wikitable" style="margin-left: auto; margin-right: auto;"

C7X: Add doi link

2025-05-01T19:55:05Z

Add doi link

← Older revision		Revision as of 19:55, 1 May 2025
Line 2:		Line 2:
	'''Hydra''' is a [[BB(2,5)]] [[Cryptid]]. Its high-level rules were first reported [https://discord.com/channels/960643023006490684/1084047886494470185/1231110668288135208 on Discord] by Daniel Yuan on 20 April 2024, who also gave Hydra said name. Later on, a 6-state, 2-symbol [[Turing machine]] was discovered and named [[Antihydra]] for having similar behaviour to Hydra, making the study of this machine important to the study of that one.		'''Hydra''' is a [[BB(2,5)]] [[Cryptid]]. Its high-level rules were first reported [https://discord.com/channels/960643023006490684/1084047886494470185/1231110668288135208 on Discord] by Daniel Yuan on 20 April 2024, who also gave Hydra said name. Later on, a 6-state, 2-symbol [[Turing machine]] was discovered and named [[Antihydra]] for having similar behaviour to Hydra, making the study of this machine important to the study of that one.

	Hydra is known to not generate Sturmian words<ref>DUBICKAS A. ON INTEGER SEQUENCES GENERATED BY LINEAR MAPS. ''Glasgow Mathematical Journal''. 2009;51(2):243-252. doi:10.1017/S0017089508004655</ref> (Corollary 4).		Hydra is known to not generate Sturmian words<ref>DUBICKAS A. ON INTEGER SEQUENCES GENERATED BY LINEAR MAPS. ''Glasgow Mathematical Journal''. 2009;51(2):243-252. doi:[https://doi.org/10.1017/S0017089508004655 10.1017/S0017089508004655]</ref> (Corollary 4).
	<div style="width: fit-content; text-align: center; margin-left: auto; margin-right: auto;">		<div style="width: fit-content; text-align: center; margin-left: auto; margin-right: auto;">
	{\|class="wikitable" style="margin-left: auto; margin-right: auto;"		{\|class="wikitable" style="margin-left: auto; margin-right: auto;"

Cosmo at 12:33, 1 May 2025

2025-05-01T12:33:23Z

← Older revision		Revision as of 12:33, 1 May 2025
Line 1:		Line 1:
	{{machine\|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA}}{{unsolved\|Does Hydra run forever?}}{{TM\|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA\|undecided}}		{{machine\|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA}}{{unsolved\|Does Hydra run forever?}}{{TM\|1RB3RB---3LA1RA_2LA3RA4LB0LB0LA\|undecided}}
	'''Hydra''' is a [[BB(2,5)]] [[Cryptid]]. Its high-level rules were first reported [https://discord.com/channels/960643023006490684/1084047886494470185/1231110668288135208 on Discord] by Daniel Yuan on 20 April 2024, who also gave Hydra said name. Later on, a 6-state, 2-symbol [[Turing machine]] was discovered and named [[Antihydra]] for having similar behaviour to Hydra, making the study of this machine important to the study of that one.		'''Hydra''' is a [[BB(2,5)]] [[Cryptid]]. Its high-level rules were first reported [https://discord.com/channels/960643023006490684/1084047886494470185/1231110668288135208 on Discord] by Daniel Yuan on 20 April 2024, who also gave Hydra said name. Later on, a 6-state, 2-symbol [[Turing machine]] was discovered and named [[Antihydra]] for having similar behaviour to Hydra, making the study of this machine important to the study of that one.

			Hydra is known to not generate Sturmian words<ref>DUBICKAS A. ON INTEGER SEQUENCES GENERATED BY LINEAR MAPS. ''Glasgow Mathematical Journal''. 2009;51(2):243-252. doi:10.1017/S0017089508004655</ref> (Corollary 4).
	<div style="width: fit-content; text-align: center; margin-left: auto; margin-right: auto;">		<div style="width: fit-content; text-align: center; margin-left: auto; margin-right: auto;">
	{\|class="wikitable" style="margin-left: auto; margin-right: auto;"		{\|class="wikitable" style="margin-left: auto; margin-right: auto;"

MrSolis at 11:10, 14 April 2025

2025-04-14T11:10:23Z

← Older revision		Revision as of 11:10, 14 April 2025
Line 49:		Line 49:
	It takes 20 steps to reach the configuration <math>C(3,0)</math>, and from there, the [[Collatz-like]] rules are repeatedly applied. Simulating Hydra has shown that after 4000000 rule steps, we have <math>b=2005373</math>. Here are the first few:		It takes 20 steps to reach the configuration <math>C(3,0)</math>, and from there, the [[Collatz-like]] rules are repeatedly applied. Simulating Hydra has shown that after 4000000 rule steps, we have <math>b=2005373</math>. Here are the first few:
	<math display="block">\begin{array}{\|c\|}\hline C(3,0)\xrightarrow{55}C(6,2)\xrightarrow{133}C(12,1)\xrightarrow{364}C(21,0)\xrightarrow{856}C(33,2)\xrightarrow{1938}C(51,4)\xrightarrow{4367}C(78,6)\rightarrow\cdots\\\hline\end{array}</math>		<math display="block">\begin{array}{\|c\|}\hline C(3,0)\xrightarrow{55}C(6,2)\xrightarrow{133}C(12,1)\xrightarrow{364}C(21,0)\xrightarrow{856}C(33,2)\xrightarrow{1938}C(51,4)\xrightarrow{4367}C(78,6)\rightarrow\cdots\\\hline\end{array}</math>
	The heuristic argument that suggests Antihydra is a [[probviously]] ~~nonhalting~~ machine can be applied here. This means that if <math>b</math> is to be thought of as moving randomly, then the probability of Hydra halting is <math display="inline">{\Big(\frac{\sqrt{5}-1}{2}\Big)}^{2005374}\approx 4.168\times 10^{-419099}</math>.		The heuristic argument that suggests Antihydra is a [[probviously]] non-halting machine can be applied here. This means that if <math>b</math> is to be thought of as moving randomly, then the probability of Hydra halting is <math display="inline">{\Big(\frac{\sqrt{5}-1}{2}\Big)}^{2005374}\approx 4.168\times 10^{-419099}</math>.
	==References==		==References==
	[[Category:Cryptids]]		[[Category:Cryptids]]

← Older revision		Revision as of 22:14, 7 October 2025
Line 23:		Line 23:
	The transition table of Hydra.</div>		The transition table of Hydra.</div>
	== Analysis ==		== Analysis ==
	Let <math>C(a,b):=0^\infty <\!\!\~~text~~{A}\;2\;0^a\;3^b\;2\;0^\infty</math>. Then,<ref>S. Ligocki, "[https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is Hard (Hydra)] (2024). Accessed 22 July 2024.</ref>		Let <math>C(a,b):=0^\infty\;\textrm{<}\textrm{A}\;2\;0^a\;3^b\;2\;0^\infty</math>. Then,<ref>S. Ligocki, "[https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is Hard (Hydra)] (2024). Accessed 22 July 2024.</ref>
	<math display="block">\begin{array}{\|lll\|}\hline		<math display="block">\begin{array}{\|lll\|}\hline
	C(2a,0)&\xrightarrow{6a^2+20a+4}&0^\infty\;3^{3a+1}\;1\;\~~text~~{A}\!\!> 2\;0^\infty,\\		C(2a,0)&\xrightarrow{6a^2+20a+4}&0^\infty\;3^{3a+1}\;1\;\textrm{A}\textrm{>}\;2\;0^\infty,\\
	C(2a,b+1)&\xrightarrow{6a^2+23a+10}&C(3a+3,b),\\		C(2a,b+1)&\xrightarrow{6a^2+23a+10}&C(3a+3,b),\\
	C(2a+1,b)&\xrightarrow{4b+6a^2+23a+26}&C(3a+3,b+2).\\\hline		C(2a+1,b)&\xrightarrow{4b+6a^2+23a+26}&C(3a+3,b+2).\\\hline
	\end{array}</math>		\end{array}</math>
	<div class="toccolours mw-collapsible mw-collapsed">'''Proof'''<div class="mw-collapsible-content">		<div class="toccolours mw-collapsible mw-collapsed">'''Proof'''<div class="mw-collapsible-content">
	Consider the partial configuration <math>P(m,n):=0^\infty\;3^m\;\~~text~~{A}\!\!>02\;0^n</math>. After 14 steps this configuration becomes		Consider the partial configuration <math>P(m,n):=0^\infty\;3^m\;\textrm{A}\textrm{>}\;02\;0^n</math>. After 14 steps this configuration becomes
	<math>0^\infty\;3^{m+3}<\!\!\~~text~~{A}\;2\;0^{n-2}</math>. We note the following shift rule:		<math>0^\infty\;3^{m+3}\;\textrm{<}\textrm{A}\;2\;0^{n-2}</math>. We note the following shift rule:
	<math display="block">\begin{array}{\|c\|}\hline3^s<\!\!\~~text~~{A}\xrightarrow{s}\;<\~~!\!\text~~{A}\;3^s\\\hline\end{array}</math>		<math display="block">\begin{array}{\|c\|}\hline3^s\;\textrm{<}\textrm{A}\xrightarrow{s}\textrm{<}\textrm{A}\;3^s\\\hline\end{array}</math>
	Using this shift rule, we get <math>0^\infty<\!\!\~~text~~{A}\;3^{m+3}\;2\;0^{n-2}</math> in <math>m+3</math> steps. From here, we can observe that <math>\~~text~~{A}\!\!>0\;3^s</math> turns into <math>3\;\~~text~~{A}\!\!>0\;3^{s-1}</math> in three steps if <math>s\ge 1</math>. By repeating this process, we acquire this transition rule:		Using this shift rule, we get <math>0^\infty\;\textrm{<}\textrm{A}\;3^{m+3}\;2\;0^{n-2}</math> in <math>m+3</math> steps. From here, we can observe that <math>\textrm{A}\textrm{>}\;0\;3^s</math> turns into <math>3\;\textrm{A}\textrm{>}\;0\;3^{s-1}</math> in three steps if <math>s\ge 1</math>. By repeating this process, we acquire this transition rule:
	<math display="block">\begin{array}{\|c\|}\hline\~~text~~{A}\!\!>0\;3^s\xrightarrow{3s}3^s\;\~~text~~{A}\!\!>0\\\hline\end{array}</math>		<math display="block">\begin{array}{\|c\|}\hline\textrm{A}\textrm{>}\;0\;3^s\xrightarrow{3s}3^s\;\textrm{A}\textrm{>}\;0\\\hline\end{array}</math>
	With this rule, it takes <math>3m+9</math> steps to reach the configuration <math>0^\infty\;3^{m+3}\;\~~text~~{A}\!\!>02\;0^{n-2}</math>, which is the same configuration as <math>P(m+3,n-2)</math>. To summarize:		With this rule, it takes <math>3m+9</math> steps to reach the configuration <math>0^\infty\;3^{m+3}\;\textrm{A}\textrm{>}\;02\;0^{n-2}</math>, which is the same configuration as <math>P(m+3,n-2)</math>. To summarize:
	<math display="block">\begin{array}{\|c\|}\hline P(m,n)\xrightarrow{4m+26}P(m+3,n-2)\text{ if }n\ge 2.\\\hline\end{array}</math>		<math display="block">\begin{array}{\|c\|}\hline P(m,n)\xrightarrow{4m+26}P(m+3,n-2)\text{ if }n\ge 2.\\\hline\end{array}</math>
	With <math>C(a,b)</math> we have <math>P(0,a)</math>. As a result, we can apply this rule <math display="inline">\big\lfloor\frac{1}{2}a\big\rfloor</math> times, which creates two possible scenarios:		With <math>C(a,b)</math> we have <math>P(0,a)</math>. As a result, we can apply this rule <math display="inline">\big\lfloor\frac{1}{2}a\big\rfloor</math> times, which creates two possible scenarios:
	#If <math>a\equiv0\ (\operatorname{mod}2)</math>, then in <math>\sum_{i=0}^{(a/2)-1}(4\times 3i+26)=\textstyle\frac{3}{2}a^2+10a</math> steps we arrive at <math display="inline">P\Big(\frac{3}{2}a,0\Big)</math>. The matching complete configuration is <math>0^\infty\;3^{(3/2)a}\;\~~text~~{A}\!\!>02\;3^b\;2\;0^\infty</math>, which in four steps becomes <math>0^\infty\;3^{(3/2)a+1}\;1\;\~~text~~{A}\!\!>3^b\;2\;0^\infty.</math> If <math>b=0</math> then we have reached the undefined <code>A2</code> transition in <math display="inline">\frac{3}{2}a^2+10a+4</math> steps total. Otherwise, continuing for three steps gives us <math>0^\infty\;3^{(3/2)+2}<\!\!\~~text~~{B}\;0\;3^{b-1}\;2\;0^\infty</math>. Another shift rule is required here:<math display="block">\begin{array}{\|c\|}\hline3^s<\!\!\~~text~~{B}\xrightarrow{s}\;<\~~!\!\text~~{B}\;0^s\\\hline\end{array}</math>This means the configuration becomes <math>0^\infty<\!\!\~~text~~{B}\;0^{(3/2)a+3}\;3^{b-1}\;2\;0^\infty</math> in <math display="inline">\frac{3}{2}a+2</math> steps, and <math>0^\infty<\!\!\~~text~~{A}\;2\;0^{(3/2)a+3}\;3^{b-1}\;2\;0^\infty</math>, equal to <math display="inline">C\Big(\frac{3}{2}a+3,b-1\Big)</math>, one step later. This gives a total of <math display="inline">\frac{3}{2}a^2+\frac{23}{2}a+10</math> steps.		#If <math>a\equiv0\ (\operatorname{mod}2)</math>, then in <math>\sum_{i=0}^{(a/2)-1}(4\times 3i+26)=\textstyle\frac{3}{2}a^2+10a</math> steps we arrive at <math display="inline">P\Big(\frac{3}{2}a,0\Big)</math>. The matching complete configuration is <math>0^\infty\;3^{(3/2)a}\;\textrm{A}\textrm{>}\;02\;3^b\;2\;0^\infty</math>, which in four steps becomes <math>0^\infty\;3^{(3/2)a+1}\;1\;\textrm{A}\textrm{>}\;3^b\;2\;0^\infty.</math> If <math>b=0</math> then we have reached the undefined <code>A2</code> transition in <math display="inline">\frac{3}{2}a^2+10a+4</math> steps total. Otherwise, continuing for three steps gives us <math>0^\infty\;3^{(3/2)+2}\;\textrm{<}\textrm{B}\;0\;3^{b-1}\;2\;0^\infty</math>. Another shift rule is required here:<math display="block">\begin{array}{\|c\|}\hline3^s\;\textrm{<}\textrm{B}\xrightarrow{s}\textrm{<}\textrm{B}\;0^s\\\hline\end{array}</math>This means the configuration becomes <math>0^\infty\;\textrm{<}\textrm{B}\;0^{(3/2)a+3}\;3^{b-1}\;2\;0^\infty</math> in <math display="inline">\frac{3}{2}a+2</math> steps, and <math>0^\infty\;\textrm{<}\textrm{A}\;2\;0^{(3/2)a+3}\;3^{b-1}\;2\;0^\infty</math>, equal to <math display="inline">C\Big(\frac{3}{2}a+3,b-1\Big)</math>, one step later. This gives a total of <math display="inline">\frac{3}{2}a^2+\frac{23}{2}a+10</math> steps.
	#If <math>a\equiv1\ (\operatorname{mod}2)</math>, then in <math display="inline">\frac{3}{2}a^2+7a-\frac{17}{2}</math> steps we arrive at <math display="inline">P\Big(\frac{3a-3}{2},1\Big)</math>. The matching complete configuration is <math>0^\infty\;3^{(3a-3)/2}\;\~~text~~{A}\!\!>020\;3^b\;2\;0^\infty</math>, which in four steps becomes <math>0^\infty\;3^{(3a-1)/2}\;1\;\~~text~~{A}\!\!>0\;3^b\;2\;0^\infty</math>, and then <math>0^\infty\;3^{(3a-1)/2}\;1\;3^b\;\~~text~~{A}\!\!>02\;0^\infty</math> in <math>3b</math> steps. After 14 steps, we see the configuration <math>0^\infty\;3^{(3a-1)/2}\;1\;3^{b+3}<\!\!\~~text~~{A}\;2\;0^\infty</math>, which turns into <math>0^\infty\;3^{(3a-1)/2}\;1<\!\!\~~text~~{A}\;3^{b+3}\;2\;0^\infty</math> in <math>b+3</math> steps. In two steps we get <math>0^\infty\;3^{(3a+1)/2}<\!\!\~~text~~{B}\;0\;3^{b+2}\;2\;0^\infty</math>, followed by <math>0^\infty<\!\!\~~text~~{B}\;0^{(3a+3)/2}\;3^{b+2}\;2\;0^\infty</math> after <math display="inline">\frac{3a+1}{2}</math> more steps. We conclude with <math>0^\infty<\!\!\~~text~~{A}\;2\;0^{(3a+3)/2}\;3^{b+2}\;2\;0^\infty</math>, equal to <math display="inline">C\Big(\frac{3a+3}{2},b+2\Big)</math>, one step later. This gives a total of <math display="inline">4b+\frac{3}{2}a^2+\frac{17}{2}a+16</math> steps.		#If <math>a\equiv1\ (\operatorname{mod}2)</math>, then in <math display="inline">\frac{3}{2}a^2+7a-\frac{17}{2}</math> steps we arrive at <math display="inline">P\Big(\frac{3a-3}{2},1\Big)</math>. The matching complete configuration is <math>0^\infty\;3^{(3a-3)/2}\;\textrm{A}\textrm{>}\;020\;3^b\;2\;0^\infty</math>, which in four steps becomes <math>0^\infty\;3^{(3a-1)/2}\;1\;\textrm{A}\textrm{>}\;0\;3^b\;2\;0^\infty</math>, and then <math>0^\infty\;3^{(3a-1)/2}\;1\;3^b\;\textrm{A}\textrm{>}\;02\;0^\infty</math> in <math>3b</math> steps. After 14 steps, we see the configuration <math>0^\infty\;3^{(3a-1)/2}\;1\;3^{b+3}\;\textrm{<}\textrm{A}\;2\;0^\infty</math>, which turns into <math>0^\infty\;3^{(3a-1)/2}\;1\;\textrm{<}\textrm{A}\;3^{b+3}\;2\;0^\infty</math> in <math>b+3</math> steps. In two steps we get <math>0^\infty\;3^{(3a+1)/2}\;\textrm{<}\textrm{B}\;0\;3^{b+2}\;2\;0^\infty</math>, followed by <math>0^\infty\;\textrm{<}\textrm{B}\;0^{(3a+3)/2}\;3^{b+2}\;2\;0^\infty</math> after <math display="inline">\frac{3a+1}{2}</math> more steps. We conclude with <math>0^\infty\;\textrm{<}\textrm{A}\;2\;0^{(3a+3)/2}\;3^{b+2}\;2\;0^\infty</math>, equal to <math display="inline">C\Big(\frac{3a+3}{2},b+2\Big)</math>, one step later. This gives a total of <math display="inline">4b+\frac{3}{2}a^2+\frac{17}{2}a+16</math> steps.
	The information above can be summarized as		The information above can be summarized as
	<math display="block">C(a,b)\rightarrow\begin{cases}0^\infty\;3^{(3/2)a+1}\;1\;\~~text~~{A}\!\!>2\;0^\infty&\text{if }a\equiv0\pmod{2}\text{ and }b=0,\\C\Big(\frac{3}{2}a+3,b-1\Big)&\text{if }a\equiv0\pmod{2}\text{ and }b>0,\\C\Big(\frac{3a+3}{2},b+2\Big)&\text{if }a\equiv1\pmod2.\end{cases}</math>		<math display="block">C(a,b)\rightarrow\begin{cases}0^\infty\;3^{(3/2)a+1}\;1\;\textrm{A}\textrm{>}\;2\;0^\infty&\text{if }a\equiv0\pmod{2}\text{ and }b=0,\\C\Big(\frac{3}{2}a+3,b-1\Big)&\text{if }a\equiv0\pmod{2}\text{ and }b>0,\\C\Big(\frac{3a+3}{2},b+2\Big)&\text{if }a\equiv1\pmod2.\end{cases}</math>
	Substituting <math>a\leftarrow 2a</math> for the first two cases and <math>a\leftarrow 2a+1</math> for the third yields the final result.		Substituting <math>a\leftarrow 2a</math> for the first two cases and <math>a\leftarrow 2a+1</math> for the third yields the final result.
	</div></div>		</div></div>
Line 52:		Line 52:
	<math display="block">\begin{array}{\|c\|}\hline C(3,0)\xrightarrow{55}C(6,2)\xrightarrow{133}C(12,1)\xrightarrow{364}C(21,0)\xrightarrow{856}C(33,2)\xrightarrow{1938}C(51,4)\xrightarrow{4367}C(78,6)\rightarrow\cdots\\\hline\end{array}</math>		<math display="block">\begin{array}{\|c\|}\hline C(3,0)\xrightarrow{55}C(6,2)\xrightarrow{133}C(12,1)\xrightarrow{364}C(21,0)\xrightarrow{856}C(33,2)\xrightarrow{1938}C(51,4)\xrightarrow{4367}C(78,6)\rightarrow\cdots\\\hline\end{array}</math>
	The heuristic argument that suggests Antihydra is a [[probviously]] non-halting machine can be applied here. This means that if <math>b</math> is to be thought of as moving randomly, then the probability of Hydra halting is <math display="inline">{\Big(\frac{\sqrt{5}-1}{2}\Big)}^{2005374}\approx 4.168\times 10^{-419099}</math>.		The heuristic argument that suggests Antihydra is a [[probviously]] non-halting machine can be applied here. This means that if <math>b</math> is to be thought of as moving randomly, then the probability of Hydra halting is <math display="inline">{\Big(\frac{\sqrt{5}-1}{2}\Big)}^{2005374}\approx 4.168\times 10^{-419099}</math>.

	== Code ==		== Code ==

← Older revision		Revision as of 16:46, 7 October 2025
Line 23:		Line 23:
	The transition table of Hydra.</div>		The transition table of Hydra.</div>
	== Analysis ==		== Analysis ==
	Let <math>C(a,b):=0^\infty\;\~~textrm~~{<A}\;2\;0^a\;3^b\;2\;0^\infty</math>. Then,<ref>S. Ligocki, "[https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is Hard (Hydra)] (2024). Accessed 22 July 2024.</ref>		Let <math>C(a,b):=0^\infty <\!\!\text{A}\;2\;0^a\;3^b\;2\;0^\infty</math>. Then,<ref>S. Ligocki, "[https://www.sligocki.com/2024/05/10/bb-2-5-is-hard.html BB(2, 5) is Hard (Hydra)] (2024). Accessed 22 July 2024.</ref>
	<math display="block">\begin{array}{\|lll\|}\hline		<math display="block">\begin{array}{\|lll\|}\hline
	C(2a,0)&\xrightarrow{6a^2+20a+4}&0^\infty\;3^{3a+1}\;1\;\~~textrm~~{A>}\;2\;0^\infty,\\		C(2a,0)&\xrightarrow{6a^2+20a+4}&0^\infty\;3^{3a+1}\;1\;\text{A}\!\!> 2\;0^\infty,\\
	C(2a,b+1)&\xrightarrow{6a^2+23a+10}&C(3a+3,b),\\		C(2a,b+1)&\xrightarrow{6a^2+23a+10}&C(3a+3,b),\\
	C(2a+1,b)&\xrightarrow{4b+6a^2+23a+26}&C(3a+3,b+2).\\\hline		C(2a+1,b)&\xrightarrow{4b+6a^2+23a+26}&C(3a+3,b+2).\\\hline
	\end{array}</math>		\end{array}</math>
	<div class="toccolours mw-collapsible mw-collapsed">'''Proof'''<div class="mw-collapsible-content">		<div class="toccolours mw-collapsible mw-collapsed">'''Proof'''<div class="mw-collapsible-content">
	Consider the partial configuration <math>P(m,n):=0^\infty\;3^m\;\~~textrm~~{A>}\;02\;0^n</math>. After 14 steps this configuration becomes		Consider the partial configuration <math>P(m,n):=0^\infty\;3^m\;\text{A}\!\!>02\;0^n</math>. After 14 steps this configuration becomes
	<math>0^\infty\;3^{m+3}\;\~~textrm~~{<A}\;2\;0^{n-2}</math>. We note the following shift rule:		<math>0^\infty\;3^{m+3}<\!\!\text{A}\;2\;0^{n-2}</math>. We note the following shift rule:
	<math display="block">\begin{array}{\|c\|}\hline3^s\;\~~textrm~~{<A}\xrightarrow{s}\~~textrm~~{<A}\;3^s\\\hline\end{array}</math>		<math display="block">\begin{array}{\|c\|}\hline3^s<\!\!\text{A}\xrightarrow{s}\;<\!\!\text{A}\;3^s\\\hline\end{array}</math>
	Using this shift rule, we get <math>0^\infty\;\~~textrm~~{<A}\;3^{m+3}\;2\;0^{n-2}</math> in <math>m+3</math> steps. From here, we can observe that <math>\~~textrm~~{A>}\;0\;3^s</math> turns into <math>3\;\~~textrm~~{A>}\;0\;3^{s-1}</math> in three steps if <math>s\ge 1</math>. By repeating this process, we acquire this transition rule:		Using this shift rule, we get <math>0^\infty<\!\!\text{A}\;3^{m+3}\;2\;0^{n-2}</math> in <math>m+3</math> steps. From here, we can observe that <math>\text{A}\!\!>0\;3^s</math> turns into <math>3\;\text{A}\!\!>0\;3^{s-1}</math> in three steps if <math>s\ge 1</math>. By repeating this process, we acquire this transition rule:
	<math display="block">\begin{array}{\|c\|}\hline\~~textrm~~{A>}\;0\;3^s\xrightarrow{3s}3^s\;\~~textrm~~{A>}\;0\\\hline\end{array}</math>		<math display="block">\begin{array}{\|c\|}\hline\text{A}\!\!>0\;3^s\xrightarrow{3s}3^s\;\text{A}\!\!>0\\\hline\end{array}</math>
	With this rule, it takes <math>3m+9</math> steps to reach the configuration <math>0^\infty\;3^{m+3}\;\~~textrm~~{A>}\;02\;0^{n-2}</math>, which is the same configuration as <math>P(m+3,n-2)</math>. To summarize:		With this rule, it takes <math>3m+9</math> steps to reach the configuration <math>0^\infty\;3^{m+3}\;\text{A}\!\!>02\;0^{n-2}</math>, which is the same configuration as <math>P(m+3,n-2)</math>. To summarize:
	<math display="block">\begin{array}{\|c\|}\hline P(m,n)\xrightarrow{4m+26}P(m+3,n-2)\text{ if }n\ge 2.\\\hline\end{array}</math>		<math display="block">\begin{array}{\|c\|}\hline P(m,n)\xrightarrow{4m+26}P(m+3,n-2)\text{ if }n\ge 2.\\\hline\end{array}</math>
	With <math>C(a,b)</math> we have <math>P(0,a)</math>. As a result, we can apply this rule <math display="inline">\big\lfloor\frac{1}{2}a\big\rfloor</math> times, which creates two possible scenarios:		With <math>C(a,b)</math> we have <math>P(0,a)</math>. As a result, we can apply this rule <math display="inline">\big\lfloor\frac{1}{2}a\big\rfloor</math> times, which creates two possible scenarios:
	#If <math>a\equiv0\ (\operatorname{mod}2)</math>, then in <math>\sum_{i=0}^{(a/2)-1}(4\times 3i+26)=\textstyle\frac{3}{2}a^2+10a</math> steps we arrive at <math display="inline">P\Big(\frac{3}{2}a,0\Big)</math>. The matching complete configuration is <math>0^\infty\;3^{(3/2)a}\;\~~textrm~~{A>}\;02\;3^b\;2\;0^\infty</math>, which in four steps becomes <math>0^\infty\;3^{(3/2)a+1}\;1\;\~~textrm~~{A>}\;3^b\;2\;0^\infty.</math> If <math>b=0</math> then we have reached the undefined <code>A2</code> transition in <math display="inline">\frac{3}{2}a^2+10a+4</math> steps total. Otherwise, continuing for three steps gives us <math>0^\infty\;3^{(3/2)+2}\;\~~textrm~~{<B}\;0\;3^{b-1}\;2\;0^\infty</math>. Another shift rule is required here:<math display="block">\begin{array}{\|c\|}\hline3^s\;\~~textrm~~{<B}\xrightarrow{s}\~~textrm~~{<B}\;0^s\\\hline\end{array}</math>This means the configuration becomes <math>0^\infty\;\~~textrm~~{<B}\;0^{(3/2)a+3}\;3^{b-1}\;2\;0^\infty</math> in <math display="inline">\frac{3}{2}a+2</math> steps, and <math>0^\infty\;\~~textrm~~{<A}\;2\;0^{(3/2)a+3}\;3^{b-1}\;2\;0^\infty</math>, equal to <math display="inline">C\Big(\frac{3}{2}a+3,b-1\Big)</math>, one step later. This gives a total of <math display="inline">\frac{3}{2}a^2+\frac{23}{2}a+10</math> steps.		#If <math>a\equiv0\ (\operatorname{mod}2)</math>, then in <math>\sum_{i=0}^{(a/2)-1}(4\times 3i+26)=\textstyle\frac{3}{2}a^2+10a</math> steps we arrive at <math display="inline">P\Big(\frac{3}{2}a,0\Big)</math>. The matching complete configuration is <math>0^\infty\;3^{(3/2)a}\;\text{A}\!\!>02\;3^b\;2\;0^\infty</math>, which in four steps becomes <math>0^\infty\;3^{(3/2)a+1}\;1\;\text{A}\!\!>3^b\;2\;0^\infty.</math> If <math>b=0</math> then we have reached the undefined <code>A2</code> transition in <math display="inline">\frac{3}{2}a^2+10a+4</math> steps total. Otherwise, continuing for three steps gives us <math>0^\infty\;3^{(3/2)+2}<\!\!\text{B}\;0\;3^{b-1}\;2\;0^\infty</math>. Another shift rule is required here:<math display="block">\begin{array}{\|c\|}\hline3^s<\!\!\text{B}\xrightarrow{s}\;<\!\!\text{B}\;0^s\\\hline\end{array}</math>This means the configuration becomes <math>0^\infty<\!\!\text{B}\;0^{(3/2)a+3}\;3^{b-1}\;2\;0^\infty</math> in <math display="inline">\frac{3}{2}a+2</math> steps, and <math>0^\infty<\!\!\text{A}\;2\;0^{(3/2)a+3}\;3^{b-1}\;2\;0^\infty</math>, equal to <math display="inline">C\Big(\frac{3}{2}a+3,b-1\Big)</math>, one step later. This gives a total of <math display="inline">\frac{3}{2}a^2+\frac{23}{2}a+10</math> steps.
	#If <math>a\equiv1\ (\operatorname{mod}2)</math>, then in <math display="inline">\frac{3}{2}a^2+7a-\frac{17}{2}</math> steps we arrive at <math display="inline">P\Big(\frac{3a-3}{2},1\Big)</math>. The matching complete configuration is <math>0^\infty\;3^{(3a-3)/2}\;\~~textrm~~{A>}\;020\;3^b\;2\;0^\infty</math>, which in four steps becomes <math>0^\infty\;3^{(3a-1)/2}\;1\;\~~textrm~~{A>}\;0\;3^b\;2\;0^\infty</math>, and then <math>0^\infty\;3^{(3a-1)/2}\;1\;3^b\;\~~textrm~~{A>}\;02\;0^\infty</math> in <math>3b</math> steps. After 14 steps, we see the configuration <math>0^\infty\;3^{(3a-1)/2}\;1\;3^{b+3}\;\~~textrm~~{<A}\;2\;0^\infty</math>, which turns into <math>0^\infty\;3^{(3a-1)/2}\;1\;\~~textrm~~{<A}\;3^{b+3}\;2\;0^\infty</math> in <math>b+3</math> steps. In two steps we get <math>0^\infty\;3^{(3a+1)/2}\;\~~textrm~~{<B}\;0\;3^{b+2}\;2\;0^\infty</math>, followed by <math>0^\infty\;\~~textrm~~{<B}\;0^{(3a+3)/2}\;3^{b+2}\;2\;0^\infty</math> after <math display="inline">\frac{3a+1}{2}</math> more steps. We conclude with <math>0^\infty\;\~~textrm~~{<A}\;2\;0^{(3a+3)/2}\;3^{b+2}\;2\;0^\infty</math>, equal to <math display="inline">C\Big(\frac{3a+3}{2},b+2\Big)</math>, one step later. This gives a total of <math display="inline">4b+\frac{3}{2}a^2+\frac{17}{2}a+16</math> steps.		#If <math>a\equiv1\ (\operatorname{mod}2)</math>, then in <math display="inline">\frac{3}{2}a^2+7a-\frac{17}{2}</math> steps we arrive at <math display="inline">P\Big(\frac{3a-3}{2},1\Big)</math>. The matching complete configuration is <math>0^\infty\;3^{(3a-3)/2}\;\text{A}\!\!>020\;3^b\;2\;0^\infty</math>, which in four steps becomes <math>0^\infty\;3^{(3a-1)/2}\;1\;\text{A}\!\!>0\;3^b\;2\;0^\infty</math>, and then <math>0^\infty\;3^{(3a-1)/2}\;1\;3^b\;\text{A}\!\!>02\;0^\infty</math> in <math>3b</math> steps. After 14 steps, we see the configuration <math>0^\infty\;3^{(3a-1)/2}\;1\;3^{b+3}<\!\!\text{A}\;2\;0^\infty</math>, which turns into <math>0^\infty\;3^{(3a-1)/2}\;1<\!\!\text{A}\;3^{b+3}\;2\;0^\infty</math> in <math>b+3</math> steps. In two steps we get <math>0^\infty\;3^{(3a+1)/2}<\!\!\text{B}\;0\;3^{b+2}\;2\;0^\infty</math>, followed by <math>0^\infty<\!\!\text{B}\;0^{(3a+3)/2}\;3^{b+2}\;2\;0^\infty</math> after <math display="inline">\frac{3a+1}{2}</math> more steps. We conclude with <math>0^\infty<\!\!\text{A}\;2\;0^{(3a+3)/2}\;3^{b+2}\;2\;0^\infty</math>, equal to <math display="inline">C\Big(\frac{3a+3}{2},b+2\Big)</math>, one step later. This gives a total of <math display="inline">4b+\frac{3}{2}a^2+\frac{17}{2}a+16</math> steps.
	The information above can be summarized as		The information above can be summarized as
	<math display="block">C(a,b)\rightarrow\begin{cases}0^\infty\;3^{(3/2)a+1}\;1\;\~~textrm~~{A>}\;2\;0^\infty&\text{if }a\equiv0\pmod{2}\text{ and }b=0,\\C\Big(\frac{3}{2}a+3,b-1\Big)&\text{if }a\equiv0\pmod{2}\text{ and }b>0,\\C\Big(\frac{3a+3}{2},b+2\Big)&\text{if }a\equiv1\pmod2.\end{cases}</math>		<math display="block">C(a,b)\rightarrow\begin{cases}0^\infty\;3^{(3/2)a+1}\;1\;\text{A}\!\!>2\;0^\infty&\text{if }a\equiv0\pmod{2}\text{ and }b=0,\\C\Big(\frac{3}{2}a+3,b-1\Big)&\text{if }a\equiv0\pmod{2}\text{ and }b>0,\\C\Big(\frac{3a+3}{2},b+2\Big)&\text{if }a\equiv1\pmod2.\end{cases}</math>
	Substituting <math>a\leftarrow 2a</math> for the first two cases and <math>a\leftarrow 2a+1</math> for the third yields the final result.		Substituting <math>a\leftarrow 2a</math> for the first two cases and <math>a\leftarrow 2a+1</math> for the third yields the final result.
	</div></div>		</div></div>