Hydra function - Revision history

Int-y1: math format

2025-10-08T08:48:19Z

math format

← Older revision		Revision as of 08:48, 8 October 2025
Line 101:		Line 101:
	<math display="block">\begin{array}{l}		<math display="block">\begin{array}{l}
	H(2n)&=&3n,\\		H(2n)&=&3n,\\
	H(2n+1)&=&3n+1.\\		H(2n+1)&=&3n+1.
	\end{array}</math>		\end{array}</math>
	Now assume that for some positive integer <math>s</math> and every odd integer <math>t</math>, <math>H^s(2^st)=3^st</math> and <math>H^s(2^st+1)=3^st+1</math>, where <math>H^i(n)</math> is function iteration. Notice that we can write <math>2^{s+1}t=2\cdot2^st</math> and <math>2^{s+1}t+1=2\cdot2^st+1</math>, so if we apply <math>H</math> to these numbers, we get <math>H(2\cdot2^st)=3\cdot 2^st</math> and <math>H(2\cdot2^st+1)=3\cdot2^st+1</math>. Now, if we apply <math>H</math> to these numbers <math>s</math> times, we get <math>H^{s+1}\big(2^{s+1}t\big)=H^s(2^s\cdot3t)=3^{s+1}t</math> and <math>H^{s+1}\big(2^{s+1}t+1\big)=H^s(2^s\cdot3t+1)=3^{s+1}t+1</math>. Therefore, by mathematical induction we have proved the following formulas:		Now assume that for some positive integer <math>s</math> and every odd integer <math>t</math>, <math>H^s(2^st)=3^st</math> and <math>H^s(2^st+1)=3^st+1</math>, where <math>H^i(n)</math> is function iteration. Notice that we can write <math>2^{s+1}t=2\cdot2^st</math> and <math>2^{s+1}t+1=2\cdot2^st+1</math>, so if we apply <math>H</math> to these numbers, we get <math>H(2\cdot2^st)=3\cdot 2^st</math> and <math>H(2\cdot2^st+1)=3\cdot2^st+1</math>. Now, if we apply <math>H</math> to these numbers <math>s</math> times, we get <math>H^{s+1}\big(2^{s+1}t\big)=H^s(2^s\cdot3t)=3^{s+1}t</math> and <math>H^{s+1}\big(2^{s+1}t+1\big)=H^s(2^s\cdot3t+1)=3^{s+1}t+1</math>. Therefore, by mathematical induction we have proved the following formulas:
	<math display="block">\begin{array}{l}		<math display="block">\begin{array}{l}
	H^s(2^st)&=&3^st,\\		H^s(2^st)&=&3^st,\\
	H^s(2^st+1)&=&3^st+1.\\		H^s(2^st+1)&=&3^st+1.
	\end{array}</math>		\end{array}</math>
	This optimization can be directly applied to the high-level rules for Hydra and Antihydra, producing this result:		This optimization can be directly applied to the high-level rules for Hydra and Antihydra, producing this result:

Int-y1: math format

2025-10-08T07:22:07Z

math format

← Older revision		Revision as of 07:22, 8 October 2025
Line 4:		Line 4:
	<math display="block">\textstyle H(n)\equiv n+\big\lfloor\frac{1}{2}n\big\rfloor=\Big\lfloor\frac{3}{2}n\Big\rfloor=\begin{cases}		<math display="block">\textstyle H(n)\equiv n+\big\lfloor\frac{1}{2}n\big\rfloor=\Big\lfloor\frac{3}{2}n\Big\rfloor=\begin{cases}
	\frac{3n}{2}&\text{if }n\equiv0\pmod{2},\\		\frac{3n}{2}&\text{if }n\equiv0\pmod{2},\\
	\frac{3n-1}{2}&\text{if }n\equiv1\pmod{2}.\\		\frac{3n-1}{2}&\text{if }n\equiv1\pmod{2}.
	\end{cases}</math>		\end{cases}</math>
	It is named as such because of its connection to the unsolved halting problems for the [[Cryptids]] [[Hydra]] and [[Antihydra]]. Due to its simplicity, simulations for both of these [[Turing machines]] utilize this function instead of what can initially be proven.		It is named as such because of its connection to the unsolved halting problems for the [[Cryptids]] [[Hydra]] and [[Antihydra]]. Due to its simplicity, simulations for both of these [[Turing machines]] utilize this function instead of what can initially be proven.

MrSolis: not done…

2025-10-07T23:17:32Z

not done…

← Older revision		Revision as of 23:17, 7 October 2025
Line 12:		Line 12:
	! Hydra !! Antihydra		! Hydra !! Antihydra
	\|-align="center"		\|-align="center"
	\|Let <math>C_H(a,b):=0^\infty\;\textrm{<A}\;2\;0^{3(a-2)}\;3^b\;2\;0^\infty</math>:<math display="block">\begin{array}{\|lll\|}\hline		\|Let <math>C_H(a,b):=0^\infty\;\textrm{<}\textrm{A}\;2\;0^{3(a-2)}\;3^b\;2\;0^\infty</math>:<math display="block">\begin{array}{\|lll\|}\hline
	0^\infty\;\textrm{A>}\;0^\infty&\xrightarrow{20}&C_H(3,0),\\		0^\infty\;\textrm{A}\textrm{>}\;0^\infty&\xrightarrow{20}&C_H(3,0),\\
	C_H(2a,0)&\xrightarrow{54a^2-48a-2}&0^\infty\;3^{9a-8}\;1\;\textrm{A>}\;2\;0^\infty,\\		C_H(2a,0)&\xrightarrow{54a^2-48a-2}&0^\infty\;3^{9a-8}\;1\;\textrm{A}\textrm{>}\;2\;0^\infty,\\
	C_H(2a,b+1)&\xrightarrow{54a^2-39a-5}&C_H(3a,b),\\		C_H(2a,b+1)&\xrightarrow{54a^2-39a-5}&C_H(3a,b),\\
	C_H(2a+1,b)&\xrightarrow{4b+54a^2-3a+4}&C_H(3a+1,b+2).\\\hline		C_H(2a+1,b)&\xrightarrow{4b+54a^2-3a+4}&C_H(3a+1,b+2).\\\hline
	\end{array}</math>		\end{array}</math>
	\|Let <math>A_H(a,b):=0^\infty\;1^a\;0\;1^{b-4}\;\textrm{E>}\;0^\infty</math>:<math display="block">\begin{array}{\|lll\|}\hline		\|Let <math>A_H(a,b):=0^\infty\;1^a\;0\;1^{b-4}\;\textrm{E}\textrm{>}\;0^\infty</math>:<math display="block">\begin{array}{\|lll\|}\hline
	0^\infty\;\textrm{A>}\;0^\infty&\xrightarrow{11}&A_H(0,8),\\		0^\infty\;\textrm{A}\textrm{>}\;0^\infty&\xrightarrow{11}&A_H(0,8),\\
	A_H(a,2b)& \xrightarrow{2a+3b^2-1}& A_H(a+2,3b),\\		A_H(a,2b)& \xrightarrow{2a+3b^2-1}& A_H(a+2,3b),\\
	A_H(0,2b+1)&\xrightarrow{3b^2-3b-7}& 0^\infty\;\textrm{<F}\;110\;1^{3b-6}\;0^\infty,\\		A_H(0,2b+1)&\xrightarrow{3b^2-3b-7}& 0^\infty\;\textrm{<}\textrm{F}\;110\;1^{3b-6}\;0^\infty,\\
	A_H(a+1,2b+1)&\xrightarrow{3b^2-7}& A_H(a,3b+1).\\\hline		A_H(a+1,2b+1)&\xrightarrow{3b^2-7}& A_H(a,3b+1).\\\hline
	\end{array}</math>		\end{array}</math>
Line 30:		Line 30:
	! Hydra !! Antihydra		! Hydra !! Antihydra
	\|-align="center"		\|-align="center"
	\|Let <math>C(a,b):=0^\infty\;\textrm{<A}\;2\;0^a\;3^b\;2\;0^\infty</math>:<math display="block">\begin{array}{\|lll\|}\hline		\|Let <math>C(a,b):=0^\infty\;\textrm{<}\textrm{A}\;2\;0^a\;3^b\;2\;0^\infty</math>:<math display="block">\begin{array}{\|lll\|}\hline
	0^\infty\;\textrm{A>}\;0^\infty&\xrightarrow{20}&C(3,0),\\		0^\infty\;\textrm{A}\textrm{>}\;0^\infty&\xrightarrow{20}&C(3,0),\\
	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\;\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>
	\|Let <math>A(a,b):=0^\infty\;1^a\;0\;1^b\;\textrm{E>}\;0^\infty</math>:<math display="block">\begin{array}{\|lll\|}\hline		\|Let <math>A(a,b):=0^\infty\;1^a\;0\;1^b\;\textrm{E}\textrm{>}\;0^\infty</math>:<math display="block">\begin{array}{\|lll\|}\hline
	0^\infty\;\textrm{A>}\;0^\infty&\xrightarrow{11}&A(0,4),\\		0^\infty\;\textrm{A}\textrm{>}\;0^\infty&\xrightarrow{11}&A(0,4),\\
	A(a,2b)& \xrightarrow{2a+3b^2+12b+11}& A(a+2,3b+2),\\		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(0,2b+1)&\xrightarrow{3b^2+9b-1}& 0^\infty\;\textrm{<}\textrm{F}\;110\;1^{3b}\;0^\infty,\\
	A(a+1,2b+1)&\xrightarrow{3b^2+12b+5}& A(a,3b+3).\\\hline		A(a+1,2b+1)&\xrightarrow{3b^2+12b+5}& A(a,3b+3).\\\hline
	\end{array}</math>		\end{array}</math>
Line 112:		Line 112:
	! Hydra !! Antihydra		! Hydra !! Antihydra
	\|-align="center"		\|-align="center"
	\|Let <math>C_H(a,b):=0^\infty\;\textrm{<A}\;2\;0^{3(a-2)}\;3^b\;2\;0^\infty</math>:		\|Let <math>C_H(a,b):=0^\infty\;\textrm{<}\textrm{A}\;2\;0^{3(a-2)}\;3^b\;2\;0^\infty</math>:
	<math display="block">\begin{array}{\|lll\|}\hline		<math display="block">\begin{array}{\|lll\|}\hline
	C_H(2^st,b+s)&\xrightarrow{f_1(s,t)}&C_H(3^st,b),\\		C_H(2^st,b+s)&\xrightarrow{f_1(s,t)}&C_H(3^st,b),\\
Line 118:		Line 118:
	\end{array}</math>		\end{array}</math>
	where <math display="inline">f_1(s,t)=\frac{3t(3^s-2^s)(18(3^s+2^s)t-65)}{5}-5s</math> and <math display="inline">f_2(s,t,b)=(b+s)4s+\frac{3t(3^s-2^s)(18(3^s+2^s)t-5)}{5}</math>.		where <math display="inline">f_1(s,t)=\frac{3t(3^s-2^s)(18(3^s+2^s)t-65)}{5}-5s</math> and <math display="inline">f_2(s,t,b)=(b+s)4s+\frac{3t(3^s-2^s)(18(3^s+2^s)t-5)}{5}</math>.
	\|Let <math>A_H(a,b):=0^\infty\;1^a\;0\;1^{b-4}\;\textrm{E>}\;0^\infty</math>:<math display="block">\begin{array}{\|lll\|}\hline		\|Let <math>A_H(a,b):=0^\infty\;1^a\;0\;1^{b-4}\;\textrm{E}\textrm{>}\;0^\infty</math>:<math display="block">\begin{array}{\|lll\|}\hline
	A_H(a,2^st)& \xrightarrow{f_3(s,t,a)}& A_H(a+2s,3^st),\\		A_H(a,2^st)& \xrightarrow{f_3(s,t,a)}& A_H(a+2s,3^st),\\
	A_H(a+s,2^st+1)&\xrightarrow{f_4(s,t)}& A_H(a,3^st+1),\\\hline		A_H(a+s,2^st+1)&\xrightarrow{f_4(s,t)}& A_H(a,3^st+1),\\\hline

Qwerpiw at 19:25, 26 July 2025

2025-07-26T19:25:14Z

← Older revision		Revision as of 19:25, 26 July 2025
Line 1:		Line 1:
			[[category:Functions]]
	[[File:Hydra Spiral.png\|thumb\|185px\|A spiral-like figure that gives the first few terms of the Hydra sequences with initial values 2, 5, 8, 11, 14, and 17.]]		[[File:Hydra Spiral.png\|thumb\|185px\|A spiral-like figure that gives the first few terms of the Hydra sequences with initial values 2, 5, 8, 11, 14, and 17.]]
	The '''Hydra function''' is a [[Collatz-like]] function defined as:		The '''Hydra function''' is a [[Collatz-like]] function defined as:

Coda: /* Coding the Hydra and Antihydra problems using the Hydra function */ remove accidental new line

2025-04-23T10:46:17Z

Coding the Hydra and Antihydra problems using the Hydra function: remove accidental new line

← Older revision		Revision as of 10:46, 23 April 2025
Line 96:		Line 96:

	Determining whether these programs halt or not (and if so, after how many loop iterations) would resolve these open problems.		Determining whether these programs halt or not (and if so, after how many loop iterations) would resolve these open problems.


	~~problems.~~

	==Properties==		==Properties==
	The Hydra function can be rewritten as follows:		The Hydra function can be rewritten as follows:

Coda: /* Coding the Hydra and Antihydra problems using the Hydra function */ Improve wording around condition counter and explain meaning of program halting status

2025-04-23T10:45:03Z

Coding the Hydra and Antihydra problems using the Hydra function: Improve wording around condition counter and explain meaning of program halting status

← Older revision		Revision as of 10:45, 23 April 2025
Line 75:		Line 75:

	=== Coding the Hydra and Antihydra problems using the Hydra function ===		=== Coding the Hydra and Antihydra problems using the Hydra function ===
	Paired with the corresponding even/odd condition counter, the Hydra function definition ~~allows one~~ to write computer programs that simulate the abstracted behavior of the Hydra and Antihydra Turing machines. The following Python program is a Hydra simulator:		Paired with the corresponding even/odd criterion as loop halting condition (implemented as a counter variable) and initial Hydra function value, the Hydra function definition can be used to write computer programs that simulate the abstracted behavior of the Hydra and Antihydra Turing machines. The following Python program is a Hydra simulator:
	<syntaxhighlight lang="python" line="1">		<syntaxhighlight lang="python" line="1">
	# 'a' and 'b' fulfill the same purpose as in the Hydra rules:		# 'a' and 'b' fulfill the same purpose as in the Hydra rules:
Line 94:		Line 94:
	</syntaxhighlight>		</syntaxhighlight>
	Replacing <code>a = 3</code> with <code>a = 8</code> and swapping <code>b -= 1</code> with <code>b += 2</code> turns this program into an Antihydra simulator.		Replacing <code>a = 3</code> with <code>a = 8</code> and swapping <code>b -= 1</code> with <code>b += 2</code> turns this program into an Antihydra simulator.

			Determining whether these programs halt or not (and if so, after how many loop iterations) would resolve these open problems.


			problems.

	==Properties==		==Properties==
	The Hydra function can be rewritten as follows:		The Hydra function can be rewritten as follows:

Coda: Emphasize the distinction between the Hydra function and -problems and add more code comments

2025-04-23T10:03:07Z

Emphasize the distinction between the Hydra function and -problems and add more code comments

← Older revision		Revision as of 10:03, 23 April 2025
Line 6:		Line 6:
	\end{cases}</math>		\end{cases}</math>
	It is named as such because of its connection to the unsolved halting problems for the [[Cryptids]] [[Hydra]] and [[Antihydra]]. Due to its simplicity, simulations for both of these [[Turing machines]] utilize this function instead of what can initially be proven.		It is named as such because of its connection to the unsolved halting problems for the [[Cryptids]] [[Hydra]] and [[Antihydra]]. Due to its simplicity, simulations for both of these [[Turing machines]] utilize this function instead of what can initially be proven.
	== Relationship to Hydra and Antihydra==		== Relationship to Hydra and Antihydra problems==
	Using the Hydra function, we can obtain simplified rules for Hydra and Antihydra:		Using the Hydra function, we can obtain simplified rules for Hydra and Antihydra:
	{\|class="wikitable"		{\|class="wikitable"
Line 73:		Line 73:
	</div></div>		</div></div>
	Under these rules, the halting problem for Hydra is about whether repeatedly applying the function <math>H(n)</math>, starting with <math>n=3</math>, will eventually generate more even terms than twice the number of odd terms. Similarly, Antihydra halts if and only if repeatedly applying <math>H(n)</math>, starting with <math>n=8</math>, will eventually generate more odd terms than twice the number of even terms.		Under these rules, the halting problem for Hydra is about whether repeatedly applying the function <math>H(n)</math>, starting with <math>n=3</math>, will eventually generate more even terms than twice the number of odd terms. Similarly, Antihydra halts if and only if repeatedly applying <math>H(n)</math>, starting with <math>n=8</math>, will eventually generate more odd terms than twice the number of even terms.
	== Coding the Hydra function ==
	~~The~~ Hydra function~~'s simple~~ definition allows one to write computer programs that simulate Hydra and Antihydra. The following Python program is a ~~straightforward~~ Hydra simulator ~~based on the Hydra function~~:		=== Coding the Hydra and Antihydra problems using the Hydra function ===
			Paired with the corresponding even/odd condition counter, the Hydra function definition allows one to write computer programs that simulate the abstracted behavior of the Hydra and Antihydra Turing machines. The following Python program is a Hydra simulator:
	<syntaxhighlight lang="python" line="1">		<syntaxhighlight lang="python" line="1">
	# 'a' and 'b' fulfill the same purpose as in the Hydra rules.		# 'a' and 'b' fulfill the same purpose as in the Hydra rules:
			# The current hydra function value
	a = 3		a = 3
			# The even/odd condition counter
	b = 0		b = 0
	# As long as Hydra has not halted, 'b' remains greater than -1.		# As long as Hydra has not halted, 'b' remains greater than -1.
Line 86:		Line 89:
	else:		else:
	b += 2		b += 2
	# This performs H(a) = a + floor(a/2).		# This performs one step of the Hydra function H(a) = a + floor(a/2).
	# Note that integer division by 2 is equivalent to one bit shift to the right (a >> 1)		# Note that integer division by 2 is equivalent to one bit shift to the right (a >> 1)
	a += a//2		a += a//2

Coda: /* Coding the Hydra function */ Note that integer division by 2 is equivalent to a right bit shift, which is relevant for the Visualizations below

2025-04-15T13:17:46Z

Coding the Hydra function: Note that integer division by 2 is equivalent to a right bit shift, which is relevant for the Visualizations below

← Older revision		Revision as of 13:17, 15 April 2025
Line 87:		Line 87:
	b += 2		b += 2
	# This performs H(a) = a + floor(a/2).		# This performs H(a) = a + floor(a/2).
			# Note that integer division by 2 is equivalent to one bit shift to the right (a >> 1)
	a += a//2		a += a//2
	</syntaxhighlight>		</syntaxhighlight>
	Replacing <code>a = 3</code> with <code>a = 8</code> and swapping <code>b -= 1</code> ~~for~~ <code>b += 2</code> turns this program into an Antihydra simulator.		Replacing <code>a = 3</code> with <code>a = 8</code> and swapping <code>b -= 1</code> with <code>b += 2</code> turns this program into an Antihydra simulator.
	==Properties==		==Properties==
	The Hydra function can be rewritten as follows:		The Hydra function can be rewritten as follows:
Line 119:		Line 120:
	== Visualizations ==		== Visualizations ==
	The four images below depict the first 1000 values of four Hydra sequences with different initial values. Each row of pixels shows a number in binary on the right and its parity on the left (blue for even, red for odd):		The four images below depict the first 1000 values of four Hydra sequences with different initial values. Each row of pixels shows a number in binary on the right and its parity on the left (blue for even, red for odd):
	<gallery mode=packed heights="250">		<gallery mode="packed" heights="250">
	File:HydraFunction-StartingValue2.png\|Starting value 2. There are 492 even numbers and 508 odd numbers.		File:HydraFunction-StartingValue2.png\|Starting value 2. There are 492 even numbers and 508 odd numbers.
	File:HydraFunction-StartingValue5.png\|Starting value 5. There are 497 even numbers and 503 odd numbers.		File:HydraFunction-StartingValue5.png\|Starting value 5. There are 497 even numbers and 503 odd numbers.

MrSolis: Rewrote Properties Section, added material from the Antihydra page that is better suited here

2025-04-14T22:12:13Z

Rewrote Properties Section, added material from the Antihydra page that is better suited here

← Older revision		Revision as of 22:12, 14 April 2025
Line 1:		Line 1:
	[[File:Hydra Spiral.png\|thumb\|185px\|A spiral-like figure that gives the first few terms of the Hydra sequences with initial values 2, 5, 8, 11, 14, and 17.]]		[[File:Hydra Spiral.png\|thumb\|185px\|A spiral-like figure that gives the first few terms of the Hydra sequences with initial values 2, 5, 8, 11, 14, and 17.]]
	The '''Hydra function''' is a [[Collatz-like]] function defined as:		The '''Hydra function''' is a [[Collatz-like]] function defined as:
	<math display="block">\textstyle H(n)\equiv n+\~~left~~\lfloor\frac{1}{2}n\~~right~~\rfloor=\Big\lfloor\frac{3}{2}n\Big\rfloor=\begin{cases}		<math display="block">\textstyle H(n)\equiv n+\big\lfloor\frac{1}{2}n\big\rfloor=\Big\lfloor\frac{3}{2}n\Big\rfloor=\begin{cases}
	\frac{3n}{2}&\text{if }n\equiv0\pmod{2},\\		\frac{3n}{2}&\text{if }n\equiv0\pmod{2},\\
	\frac{3n-1}{2}&\text{if }n\equiv1\pmod{2}.\\		\frac{3n-1}{2}&\text{if }n\equiv1\pmod{2}.\\
Line 42:		Line 42:
	\end{array}</math>		\end{array}</math>
	\|}		\|}
	Already, both machines appear to ~~have~~ very similar ~~functions~~. They have one parameter that increases exponentially with growth factor <math display="inline">\frac{3}{2}</math> and another that ~~effectively~~ takes a pseudo-random walk. Below, the exponentially increasing variables are described by integer sequences:		Already, both machines appear to be very similar. They have one parameter that increases exponentially with growth factor <math display="inline">\frac{3}{2}</math> and another that takes a pseudo-random walk. Below, the exponentially increasing variables are described by integer sequences:
	{\|class="wikitable"		{\|class="wikitable"
	! Hydra !! Antihydra		! Hydra !! Antihydra
Line 49:		Line 49:
	\|<math display="block">a_0=4,a_{n+1}=\begin{cases}\frac{3a_n+4}{2}&\text{if }a_n\equiv0\pmod{2}\\\frac{3a_n+3}{2}&\text{if }a_n\equiv1\pmod{2}\end{cases}</math>		\|<math display="block">a_0=4,a_{n+1}=\begin{cases}\frac{3a_n+4}{2}&\text{if }a_n\equiv0\pmod{2}\\\frac{3a_n+3}{2}&\text{if }a_n\equiv1\pmod{2}\end{cases}</math>
	\|}		\|}
	This ~~makes illustrating~~ the transformation easier. Now we will define a new integer sequence based on the old one and discover the recursive rules for that sequence. This new sequence is <math display="inline">b_n=\frac{1}{3}a_n+2</math> and <math>b_n=a_n+4</math> for Hydra and Antihydra respectively. We start by using <math>b_{n+1}</math> instead and substituting <math>a_{n+1}</math> for its recursive formula. By doing so, we get:		This will make demonstrating the transformation easier. Now we will define a new integer sequence based on the old one and discover the recursive rules for that sequence. This new sequence is <math display="inline">b_n=\frac{1}{3}a_n+2</math> and <math>b_n=a_n+4</math> for Hydra and Antihydra respectively. We start by using <math>b_{n+1}</math> instead and substituting <math>a_{n+1}</math> for its recursive formula. By doing so, we get:
	{\|class="wikitable"		{\|class="wikitable"
	! Hydra !! Antihydra		! Hydra !! Antihydra
Line 63:		Line 63:
	\|<math display="block">b_0=8,b_{n+1}=\begin{cases}\frac{3(b_n-4)+12}{2}&\text{if }b_n-4\equiv0\pmod{2}\\\frac{3(b_n-4)+11}{2}&\text{if }b_n-4\equiv1\pmod{2}\end{cases}</math>		\|<math display="block">b_0=8,b_{n+1}=\begin{cases}\frac{3(b_n-4)+12}{2}&\text{if }b_n-4\equiv0\pmod{2}\\\frac{3(b_n-4)+11}{2}&\text{if }b_n-4\equiv1\pmod{2}\end{cases}</math>
	\|}		\|}
	~~We note that the~~ if statements ~~simplify~~ to checking if <math>b_n</math> is even or odd. After simplifying, we are done:		The <math>\text{if}</math> statements amount to checking if <math>b_n</math> is even or odd. After simplifying, we are done:
	{\|class="wikitable"		{\|class="wikitable"
	! Hydra !! Antihydra		! Hydra !! Antihydra
Line 70:		Line 70:
	\|<math display="block">b_0=8,b_{n+1}=\begin{cases}\frac{3b_n}{2}&\text{if }b_n\equiv0\pmod{2}\\\frac{3b_n-1}{2}&\text{if }b_n\equiv1\pmod{2}\end{cases}</math>		\|<math display="block">b_0=8,b_{n+1}=\begin{cases}\frac{3b_n}{2}&\text{if }b_n\equiv0\pmod{2}\\\frac{3b_n-1}{2}&\text{if }b_n\equiv1\pmod{2}\end{cases}</math>
	\|}		\|}
	Now that we have demonstrated a strong similarity in the behaviour of both Turing machines, we can return to using the high-level rules. Doing that while ~~accounting for~~ the step counts yields the final result.		Now that we have demonstrated a strong similarity in the behaviour of both Turing machines, we can return to using the high-level rules. Doing that while considering the step counts yields the final result.
	</div></div>		</div></div>
			Under these rules, the halting problem for Hydra is about whether repeatedly applying the function <math>H(n)</math>, starting with <math>n=3</math>, will eventually generate more even terms than twice the number of odd terms. Similarly, Antihydra halts if and only if repeatedly applying <math>H(n)</math>, starting with <math>n=8</math>, will eventually generate more odd terms than twice the number of even terms.
			== Coding the Hydra function ==
			The Hydra function's simple definition allows one to write computer programs that simulate Hydra and Antihydra. The following Python program is a straightforward Hydra simulator based on the Hydra function:
			<syntaxhighlight lang="python" line="1">
			# 'a' and 'b' fulfill the same purpose as in the Hydra rules.
			a = 3
			b = 0
			# As long as Hydra has not halted, 'b' remains greater than -1.
			while b != -1:
			# If 'a' is even, decrement 'b', otherwise increase 'b' by 2.
			if a % 2 == 0:
			b -= 1
			else:
			b += 2
			# This performs H(a) = a + floor(a/2).
			a += a//2
			</syntaxhighlight>
			Replacing <code>a = 3</code> with <code>a = 8</code> and swapping <code>b -= 1</code> for <code>b += 2</code> turns this program into an Antihydra simulator.
	==Properties==		==Properties==
	The Hydra function can be rewritten as follows:		The Hydra function can be rewritten as follows:
Line 78:		Line 96:
	H(2n+1)&=&3n+1.\\		H(2n+1)&=&3n+1.\\
	\end{array}</math>		\end{array}</math>
	Now ~~we will define~~ <math>s</math> and <math>t</math> ~~to be positive integers with~~ <math>t</math> ~~additionally being odd,~~ and ~~substitute~~ <math>~~n\leftarrow~~ 2^~~{s-~~1}t</math>:		Now assume that for some positive integer <math>s</math> and every odd integer <math>t</math>, <math>H^s(2^st)=3^st</math> and <math>H^s(2^st+1)=3^st+1</math>, where <math>H^i(n)</math> is function iteration. Notice that we can write <math>2^{s+1}t=2\cdot2^st</math> and <math>2^{s+1}t+1=2\cdot2^st+1</math>, so if we apply <math>H</math> to these numbers, we get <math>H(2\cdot2^st)=3\cdot 2^st</math> and <math>H(2\cdot2^st+1)=3\cdot2^st+1</math>. Now, if we apply <math>H</math> to these numbers <math>s</math> times, we get <math>H^{s+1}\big(2^{s+1}t\big)=H^s(2^s\cdot3t)=3^{s+1}t</math> and <math>H^{s+1}\big(2^{s+1}t+1\big)=H^s(2^s\cdot3t+1)=3^{s+1}t+1</math>. Therefore, by mathematical induction we have proved the following formulas:
	<math ~~display="block"~~>~~\begin{array}{l}~~
	H(~~2^st~~)~~&=&~~2^{s-1}\~~times 3t,\\~~
	~~H(2~~^st~~+1)&=&~~2^{s-1}\~~times 3t~~+1.\\
	~~\end{array}~~</math>
	~~Because~~ <math>2^~~{s-~~1}\~~times 3t~~</math> ~~is also the result of substituting~~ <math>~~s\leftarrow s-1~~</math> ~~and~~ <math>~~t\leftarrow 3t~~</math>, we ~~can iterate the Hydra function many times. Letting~~ <math>H^k(n)=\~~underbrace~~{H(\~~cdots(~~H(~~H(n)))~~\~~cdots~~)}_{~~k\text{ times}~~}</math>, ~~this means~~:
	<math display="block">\begin{array}{l}		<math display="block">\begin{array}{l}
	H^s(2^st)&=&3^st,\\		H^s(2^st)&=&3^st,\\
Line 104:		Line 117:
	where <math display="inline">f_3(s,t,a)=(2a-3+2s)s+\frac{3t^2(9^s-4^s)}{5}</math> and <math display="inline">f_4(s,t)=\frac{3t^2(9^s-4^s)}{5}-7s</math>.		where <math display="inline">f_3(s,t,a)=(2a-3+2s)s+\frac{3t^2(9^s-4^s)}{5}</math> and <math display="inline">f_4(s,t)=\frac{3t^2(9^s-4^s)}{5}-7s</math>.
	\|}		\|}
			== Visualizations ==
			The four images below depict the first 1000 values of four Hydra sequences with different initial values. Each row of pixels shows a number in binary on the right and its parity on the left (blue for even, red for odd):
			<gallery mode=packed heights="250">
			File:HydraFunction-StartingValue2.png\|Starting value 2. There are 492 even numbers and 508 odd numbers.
			File:HydraFunction-StartingValue5.png\|Starting value 5. There are 497 even numbers and 503 odd numbers.
			File:Antihydra increasing value.png\|Starting value 8. There are 499 even numbers and 501 odd numbers.
			File:HydraFunction-StartingValue11.png\|Starting value 11. There are 481 even numbers and 519 odd numbers.
			</gallery>

MrSolis: Corrected minor errors

2025-03-10T21:47:13Z

Corrected minor errors

← Older revision		Revision as of 21:47, 10 March 2025
Line 1:		Line 1:
	[[File:Hydra Spiral.png\|thumb\|~~200px~~\|A spiral-like figure that gives the first few terms of the Hydra sequences with initial values 2, 5, 8, 11, and 17.]]		[[File:Hydra Spiral.png\|thumb\|185px\|A spiral-like figure that gives the first few terms of the Hydra sequences with initial values 2, 5, 8, 11, 14, and 17.]]
	The '''Hydra function''' is a [[Collatz-like]] function defined as:		The '''Hydra function''' is a [[Collatz-like]] function defined as:
	<math display="block">\textstyle H(n)\equiv n+\left\lfloor\frac{1}{2}n\right\rfloor=\Big\lfloor\frac{3}{2}n\Big\rfloor=\begin{cases}		<math display="block">\textstyle H(n)\equiv n+\left\lfloor\frac{1}{2}n\right\rfloor=\Big\lfloor\frac{3}{2}n\Big\rfloor=\begin{cases}
	\frac{3n}{2} & \text{if } n\equiv0\pmod{2}, \\		\frac{3n}{2}&\text{if }n\equiv0\pmod{2},\\
	\frac{3n-1}{2} & \text{if } n\equiv1\pmod{2}. \\		\frac{3n-1}{2}&\text{if }n\equiv1\pmod{2}.\\
	\end{cases}</math>		\end{cases}</math>
	It is named as such ~~due~~ its connection to the unsolved halting problems for the [[Cryptids]] [[Hydra]] and [[Antihydra]]. Due to its simplicity, simulations for both of these [[Turing machines]] utilize this function instead of what can initially be proven.		It is named as such because of its connection to the unsolved halting problems for the [[Cryptids]] [[Hydra]] and [[Antihydra]]. Due to its simplicity, simulations for both of these [[Turing machines]] utilize this function instead of what can initially be proven.
	== Relationship to Hydra and Antihydra==		== Relationship to Hydra and Antihydra==
	Using the Hydra function, we can obtain simplified rules for Hydra and Antihydra:		Using the Hydra function, we can obtain simplified rules for Hydra and Antihydra: