ในทางคณิตศาสตร์ โดยเฉพาะในทฤษฎีกราฟและทฤษฎีจำนวนเกมไฮดราเป็นเกมคณิตศาสตร์แบบวนซ้ำสำหรับผู้เล่นคนเดียวที่เล่นบนต้นไม้ทางคณิตศาสตร์ที่เรียกว่า "ไฮดรา" โดยเป้าหมายของผู้เล่นคือการ "ฆ่า" ไฮดราโดยการลบโหนด ("หัว") ออกทีละโหนด ในขณะที่ไฮดราก็ขยายตัวเองไปพร้อมกัน (ซึ่งคล้ายกับการต่อสู้ระหว่างเฮอร์คิวลีสกับไฮดราแห่งเลอร์เนียสจึงเป็นที่มาของชื่อ) กฎของเกมอนุญาตให้ผู้เล่นชนะในที่สุด แต่จำนวนขั้นตอนที่จำเป็นในการบรรลุเป้าหมายจะเพิ่มขึ้นอย่างรวดเร็วมากเมื่อขนาดของต้นไม้เริ่มต้นเพิ่มขึ้น ดังนั้นเกมนี้จึงสามารถใช้สร้างจำนวนขนาดใหญ่หรือลำดับอนันต์หรือพิสูจน์ความแข็งแกร่งของทฤษฎีทางคณิตศาสตร์บางอย่างได้^{[ 1 ]}

แตกต่างจากอัลกอริทึมเชิงการจัดเรียงแบบอื่นๆ เช่นTREEและSCGตรงที่ ไม่จำเป็นต้องค้นหาเพื่อคำนวณค่าฟังก์ชันที่เติบโตอย่างรวดเร็วเหล่านี้ เพียงแค่ต้องใช้กฎการแปลงกับต้นไม้ไปเรื่อยๆ จนกว่าเกมจะสั่งให้หยุด

เกมไฮดราแบบง่ายประกอบด้วยลำดับการทำซ้ำที่ปรับเปลี่ยนไฮดรา ซึ่งเป็นกราฟ ต้นไม้รากจำกัดที่มีรากอยู่ที่ แต่ละการทำซ้ำจะถูกกำกับด้วยหมายเลขเรียงลำดับเริ่มต้นที่ 1 และประกอบด้วยสองขั้นตอน: ${\displaystyle R}$${\displaystyle n}$

1. ผู้เล่นจะเลือกโหนดใบ จากต้นไม้ในแต่ละตา${\displaystyle x}$
2. ลบโหนดใบออกให้เป็นโหนดแม่ของถ้าให้กลับไปที่ขั้นตอนที่ 1 มิฉะนั้น ถ้าให้เป็นโหนดแม่ของจากนั้นสร้างโหนดใบเป็นลูกของโดยที่โหนดใหม่จะปรากฏต่อจากลูกที่มีอยู่ของระหว่างการท่องแบบโพสต์ออร์เดอร์ (ในทางสายตา โหนดใหม่เหล่านี้จะปรากฏทางด้านขวาของลูกที่มีอยู่) จากนั้นกลับไปที่ขั้นตอนที่ 1${\displaystyle x}$${\displaystyle a}$${\displaystyle x}$${\displaystyle a=R}$${\displaystyle a\neq R}$${\displaystyle b}$${\displaystyle a}$${\displaystyle n}$${\displaystyle b}$${\displaystyle b}$

แม้ว่าไฮดราจะเติบโตขึ้นมาโดยมีจำนวนใบไม่จำกัดในแต่ละตา แต่เกมจะจบลงในที่สุดในจำนวนขั้นตอนที่จำกัด: ถ้าคือระยะทางที่มากที่สุดระหว่างรากและใบ และ คือจำนวนใบที่ระยะนี้การอุปมานบนสามารถใช้เพื่อแสดงให้เห็นว่าผู้เล่นจะฆ่าไฮดราได้เสมอ ถ้าการเอาใบออกจะไม่ทำให้ไฮดราเติบโต ดังนั้นผู้เล่นจะชนะหลังจากตา สำหรับค่าทั่วไปเราพิจารณาการเคลื่อนไหวสองประเภท: การเคลื่อนไหวที่เกี่ยวข้องกับใบที่ระยะทางน้อยกว่าจากราก และการเคลื่อนไหวที่เกี่ยวข้องกับใบที่ระยะทางเท่ากับเนื่องจาก การเคลื่อนไหวประเภทแรกนั้นเหมือนกับการเคลื่อนไหวในเกมที่มีความลึกสมมติฐานการอุปมานบอกเราว่าหลังจากเคลื่อนไหวจำนวนจำกัดเช่นนี้ ผู้เล่นจะไม่มีทางเลือกอื่นนอกจากเลือกใบที่ความลึกไม่มีการเคลื่อนไหวใดที่สร้างโหนดใหม่ที่ความลึกนี้ ดังนั้นกระบวนการทั้งหมดนี้สามารถทำซ้ำได้สูงสุดครั้ง หลังจากนั้นจะไม่มีใบที่ความลึกอีกต่อไปและเกมจะมีระดับความลึก (อย่างมากที่สุด) เมื่อนำสมมติฐานการเหนี่ยวนำกลับมาใช้อีกครั้ง เราพบว่าในที่สุดผู้เล่นจะต้องเป็นผู้ชนะโดยรวม ${\displaystyle n}$${\displaystyle d}$${\displaystyle w}$${\displaystyle d}$${\displaystyle d=1}$${\displaystyle w}$${\displaystyle d}$${\displaystyle d}$${\displaystyle d}$${\displaystyle d-1}$${\displaystyle d}$${\displaystyle w}$${\displaystyle d}$${\displaystyle d-1}$

แม้ว่าสิ่งนี้จะแสดงให้เห็นว่าผู้เล่นจะชนะในที่สุด แต่ก็อาจใช้เวลานานมาก ตัวอย่างเช่น พิจารณาอัลกอริทึมต่อไปนี้สำหรับการเคลื่อนไหวของผู้เล่นและการตอบสนองของไฮดรา เลือกใบขวาสุด (เช่น ใบใหม่ล่าสุดซึ่งจะอยู่ในระดับที่ใกล้กับรากมากที่สุด) และกำหนดเวลาครั้งแรกครั้งที่สอง และต่อไปเรื่อย ๆโดยเพิ่มขึ้นทีละหนึ่งเสมอ หากไฮดรามีกิ่งเดียวที่มีความยาว - แล้วสำหรับไฮดราจะถูกฆ่าในขั้นตอนเดียว ในขณะที่จะถูกฆ่าในสามขั้นตอนหากต้องใช้ 11 ขั้นตอนสำหรับต้องใช้ 1114111 ขั้นตอนสำหรับได้รับการคำนวณอย่างแม่นยำ^{[ 2 ]}ให้และซ้อนกันnครั้ง จากนั้น ${\displaystyle n=1}$${\displaystyle 2}$${\displaystyle n}$${\displaystyle y}$${\displaystyle y=1}$${\displaystyle y=2}$${\displaystyle y=3}$${\displaystyle y=4}$${\displaystyle y=5}$${\displaystyle F(x)=2^{x}\cdot (x+2)-1}$${\displaystyle F^{n}(x)}$${\displaystyle F}$${\displaystyle HYDRA(5)=}$${\displaystyle 2\cdot F^{F^{2}(3)+1}(F^{2}(3)+1)+1=}$${\displaystyle 2\cdot F^{22539988369408}(22539988369408)+1}$

วิธีแก้ปัญหาทั่วไปของเกมไฮดรา (เล่นด้วยอัลกอริทึมของส่วนก่อนหน้า) มีดังนี้: ^{[ 3 ]}

ให้แทนจำนวนขั้นตอนที่จำเป็นในการลดระดับหัวที่มีความลึกnเมื่อหัวที่อยู่ใกล้รากทั้งหมดเป็นหัวเดี่ยว (ไม่มีกิ่ง "ขวา" เพิ่มเติม) ${\displaystyle F_{i}(x)}$

จากนั้นและ. ${\displaystyle F_{i+1}(x)=F_{i}^{x}(x+1)}$${\displaystyle F_{1}(x)=2\cdot (x+1)-1=2x+1}$

คำตอบคือ: ${\displaystyle hydra(n)}$${\displaystyle F_{1}(F_{2}(F_{3}(\ldots F_{n-1}(F_{n}(1))\ldots )))}$

อัตราการเติบโตของฟังก์ชันนี้เร็วกว่าลำดับชั้นการเติบโตเร็ว มาตรฐาน เนื่องจาก ตัว มัน เองเติบโตในอัตราเดียวกับลำดับชั้นการเติบโตเร็วและคำตอบคือการซ้อนกันลำดับ ที่ nของ${\displaystyle F_{i}(x)}$${\displaystyle F_{i}(x)}$

ไฮดรา แบบเคอร์บี - ปารีสถูกกำหนดโดยการปรับเปลี่ยนกฎของไฮดราแบบง่ายที่ได้นิยามไว้ข้างต้น:

• สมมติว่าเป็นโหนดแม่ของถ้า. แนบสำเนาของซับทรีที่มีรากไปยังทางด้านขวาของโหนดอื่นๆ ทั้งหมดที่เชื่อมต่อกับ. กลับไปที่ขั้นตอนที่ 2 ^{[ 4 ]}${\displaystyle b}$${\displaystyle a}$${\displaystyle a\neq R}$${\displaystyle n}$${\displaystyle a}$${\displaystyle b}$${\displaystyle b}$

แทนที่จะเพิ่มเฉพาะใบใหม่ กฎนี้จะเพิ่มสำเนาของซับทรีทั้งหมด โดยคงทุกอย่างไว้เหมือนเดิม ในครั้งนี้ต้องใช้เทิร์นต้องใช้ขั้นตอนต้องใช้ขั้นตอน และต้องใช้ขั้นตอนมากกว่าจำนวนของเกรแฮมอัตราการเติบโตของฟังก์ชันนี้มหาศาลเท่ากับในลำดับชั้นที่เติบโตอย่างรวดเร็ว โดยที่คือจำนวนเอปซิลอนที่ เล็กที่สุด${\displaystyle y=1}$${\displaystyle 1}$${\displaystyle y=2}$${\displaystyle 3}$${\displaystyle y=3}$${\displaystyle 37}$${\displaystyle y=4}$${\displaystyle f_{\varepsilon _{0}}(n)}$${\displaystyle \varepsilon _{0}}$

นี่ไม่ใช่ไฮดราที่ทรงพลังที่สุดไฮดราของบุชโฮลซ์เป็นไฮดราที่มีศักยภาพมากกว่า^{[ 5 ] มันเกี่ยวข้องกับต้นไม้ที่ มี}ป้ายกำกับ รากมีป้ายกำกับที่ไม่ซ้ำกัน (เรียกว่า ) และโหนดอื่น ๆ แต่ละโหนดมีป้ายกำกับที่เป็น จำนวนเต็มที่ไม่เป็นลบหรือ[ ^{6 ]}${\displaystyle R}$${\displaystyle \omega }$

1. ไฮดราคือต้นไม้ที่มีป้ายกำกับและมีรากจำกัด รากควรมีป้ายกำกับเป็น กำกับไว้ กำหนดป้ายกำกับให้กับทุกโหนดที่อยู่ติดกับราก(สำคัญมากเพื่อให้แน่ใจว่ารากเป็นจุดสิ้นสุดเสมอ) และทุกโหนดอื่น ๆ ด้วยจำนวนเต็มที่ไม่เป็นลบหรือ${\displaystyle R}$${\displaystyle 0}$${\displaystyle \omega }$
2. เลือกโหนดใบและเลขจำนวนเต็มบวกในแต่ละขั้น${\displaystyle x}$${\displaystyle n}$
3. เอาใบไม้ออก ให้เป็นผู้ปกครองของ ไม่มีอะไรเกิดขึ้นอีกถ้ากลับไปที่ขั้นตอนที่ 2${\displaystyle x}$${\displaystyle a}$${\displaystyle x}$${\displaystyle a=R}$
4. ถ้าป้ายกำกับของคือสมมติว่าเป็นโหนดแม่ ของ แนบ สำเนาของซับทรีที่มีรากเป็น ไปทางด้านขวาของโหนดอื่นๆ ทั้งหมดที่เชื่อมต่อกับกลับไปที่ขั้นตอนที่ 2${\displaystyle x}$${\displaystyle 0}$${\displaystyle b}$${\displaystyle a}$${\displaystyle n}$${\displaystyle a}$${\displaystyle b}$${\displaystyle b}$
5. ถ้าป้ายกำกับของ x คือให้แทนที่ด้วยกลับไปที่ขั้นตอนที่ 2${\displaystyle \omega }$${\displaystyle n+1}$
6. ถ้าป้ายกำกับของเป็นจำนวนเต็มบวกให้ลงไปตามต้นไม้เพื่อหาโหนดที่มีป้ายกำกับโหนดดังกล่าวมีอยู่จริงเพราะโหนดทั้งหมดที่อยู่ติดกับรากมีป้ายกำกับ คัดลอกซับทรีที่มีรากแทนที่ด้วยซับทรีนี้ อย่างไรก็ตาม ให้เปลี่ยนป้ายกำกับ(รากของสำเนาของซับทรี) เป็นเรียกค่าเทียบเท่าของในซับทรีที่คัดลอกมา(ดังนั้นจึงเป็นเช่นเดียวกับจึงเป็น) และเปลี่ยนป้ายกำกับเป็น0 กลับไปที่ขั้นตอนที่ 2 ^{[ 7 ]}${\displaystyle x}$${\displaystyle u}$${\displaystyle c}$${\displaystyle <u}$${\displaystyle 0}$${\displaystyle c}$${\displaystyle x}$${\displaystyle x}$${\displaystyle u-1}$${\displaystyle x}$${\displaystyle x'}$${\displaystyle x}$${\displaystyle x'}$${\displaystyle c}$${\displaystyle x}$${\displaystyle (x')}$

ที่น่าประหลาดใจคือ แม้ว่าไฮดราจะเติบโตสูงขึ้นอย่างมาก แต่ลำดับนี้ก็จบลงเสมอ^{[ 8 ]}

สำหรับเกม Kirby–Paris Hydras กฎนั้นง่ายมาก: เริ่มต้นด้วยไฮดรา ซึ่งเป็นต้นไม้รากที่ไม่มีลำดับและไม่มีป้ายกำกับในแต่ละรอบ ผู้เล่นจะเลือกโหนดใบที่จะตัด และเลือกจำนวนเต็มที่ไม่ติดลบหนึ่งจำนวนถ้า เป็นลูกของโหนดรากมันจะถูกลบออกจากต้นไม้และไม่มีอะไรเกิดขึ้นในรอบนั้น มิฉะนั้น ให้ เป็นโหนดแม่ของ และ เป็นโหนดแม่ของ ลบ ออกจากต้นไม้ จากนั้นเพิ่ม สำเนาของ ที่ถูกแก้ไข แล้ว  เป็นลูกของเกมจะจบลงเมื่อไฮดราเหลือเพียงโหนดเดียว ${\displaystyle T}$${\displaystyle c}$${\displaystyle n}$${\displaystyle c}$${\displaystyle r}$${\displaystyle p}$${\displaystyle c}$${\displaystyle g}$${\displaystyle p}$${\displaystyle c}$${\displaystyle n}$${\displaystyle p}$${\displaystyle g}$

เพื่อให้ได้ฟังก์ชันที่เติบโตอย่างรวดเร็ว เราสามารถกำหนดค่าคงที่ เช่น  ในขั้นตอนแรก จากนั้น, , และอื่นๆ และตัดสินใจใช้กฎง่ายๆ สำหรับตำแหน่งที่จะตัด เช่น เลือกใบขวาสุดเสมอ จากนั้น  คือจำนวนขั้นตอนที่จำเป็นสำหรับเกมที่จะจบลงโดยเริ่มจากเส้นทางที่มีความยาวนั่นคือ สแต็กเชิงเส้นของ  โหนดในที่สุด ครอบงำฟังก์ชันเรียกซ้ำทั้งหมดที่พิสูจน์ได้ว่าสมบูรณ์ในพีชคณิตของ Peano และพิสูจน์ได้ว่าสมบูรณ์ใน^{[ 9 ]}${\displaystyle n}$${\displaystyle n=1}$${\displaystyle n=2}$${\displaystyle n=3}$${\displaystyle \ชื่อผู้ดำเนินการ {ไฮดรา} (k)}$${\displaystyle k}$${\displaystyle k+1}$${\displaystyle \operatorname {Hydra} (k)}$${\displaystyle \mathrm {PA} +(\varepsilon _{0}{\text{ is well-ordered}})}$

สามารถแสดงสิ่งนี้ได้โดยใช้เครื่องหมายวงเล็บเหลี่ยม หลายตัวเรียงกัน :

• เริ่มต้นด้วยลำดับวงเล็บที่จำกัด เช่น.${\displaystyle (()(()(())((()))))}$
• เลือกคู่ว่างหนึ่งคู่และจำนวนเต็มที่ไม่เป็นลบหนึ่งจำนวน${\displaystyle ()}$${\displaystyle n}$
• ลบคู่ดังกล่าว และหากคู่แม่ของคู่นั้นไม่ใช่คู่ที่อยู่นอกสุด ให้เลือกคู่แม่ของคู่นั้นแล้วเพิ่ม  สำเนาเข้าไป${\displaystyle n}$

ตัวอย่างเช่น ด้วย, . ต่อไปนี้คือรายการค่าของ: ${\displaystyle n=3}$${\displaystyle (()(()\mathbf {()} ))\implies (()(())(())(())(()))}$${\displaystyle \operatorname {Hydra} (k)}$

• ${\displaystyle \operatorname {Hydra} (0)=0}$
• ${\displaystyle \operatorname {Hydra} (1)=1}$
• ${\displaystyle \operatorname {Hydra} (2)=3}$
• ${\displaystyle \operatorname {Hydra} (3)=37}$
• ${\displaystyle \operatorname {Hydra} (4)>f_{\omega \cdot 2+4}(5)\gg {\text{Graham's number}}}$
• ${\displaystyle \operatorname {Hydra} (5)>f_{\omega ^{2+4}}(5)}$
• ${\displaystyle \operatorname {Hydra} (6)>f_{\underbrace {\omega ^{\cdots ^{\omega }}} _{6}}(5)}$

เกมไฮดราของบุชโฮลซ์เป็นเกมไฮดราในตรรกศาสตร์ทางคณิตศาสตร์ เป็นเกมผู้เล่นคนเดียวที่อิงจากแนวคิดของการตัดชิ้นส่วนออกจากต้นไม้ทางคณิตศาสตร์ เกมไฮดราสามารถใช้สร้างฟังก์ชันที่เติบโตอย่างรวดเร็วซึ่งในที่สุดจะครอบงำฟังก์ชันแบบเรียกซ้ำทั้งหมดที่พิสูจน์ได้ในลำดับชั้นของทฤษฎีของนิยามอุปนัยแบบวนซ้ำมันเป็นส่วนขยายของไฮดราของเคอร์บี-ปารีส สิ่งที่เราใช้เพื่อให้ได้ฟังก์ชันที่เติบโตอย่างรวดเร็วก็เหมือนกับไฮดราของเคอร์บี-ปารีส แต่เนื่องจากไฮดราของบุชโฮลซ์เติบโตไม่เพียงแต่ในความกว้างเท่านั้น แต่ยังเติบโตในความสูงด้วย จึงมีอัตราการเติบโตที่มากกว่ามากของ ลำดับ ทาเคอุติ-เฟเฟอร์แมน-บุชโฮลซ์ : ${\displaystyle BH(n)}$${\displaystyle {\mathsf {ID}}_{\nu }}$${\displaystyle BH(n)}$${\displaystyle f_{\psi _{0}(\varepsilon _{\Omega _{\omega }+1})}(n)}$

• ${\displaystyle BH(1)=0}$
• ${\displaystyle BH(2)=1}$
• ${\displaystyle BH(3)<f_{\varepsilon _{0}}(3)}$

ระบบนี้ยังสามารถใช้สร้างสัญกรณ์ลำดับสำหรับลำดับอนันต์ได้เช่น ${\displaystyle \psi _{0}(\Omega _{\omega })=+0(\omega )}$

• ทฤษฎีบทของกูดสไตน์

• เกมไฮดรา
• เฮอร์คิวลีสกับไฮดรา
• กำจัดไฮดราทางคณิตศาสตร์โดยPBS Infinite Series