하이드라 게임

수학에서 특히 그래프 이론과 숫자 이론에서 하이드라 게임은 하이드라라고 불리는 수학 나무에서 행해지는 1인용 반복 수학 게임인데, 보통 히드라가 동시에 팽창하는 동안 히드라의 "헤드"를 잘라내는 것이 목표다.하이드라 게임은 많은 숫자나 무한정 서수를 생성하거나 특정 수학 이론의 강도를 증명하는 데 사용될 수 있다.^[1]

TREE나 SCG와 같은 조합과 달리, 이러한 빠르게 성장하는 함수 값을 계산하기 위해 검색이 필요하지 않다. 즉, 게임이 멈출 때까지 변환 규칙을 트리에 계속 적용해야 한다.

소개

간단한 히드라 게임은 다음과 같이 정의할 수 있다.

히드라는 유한한 뿌리가 있는 나무로, 루프가 없는 점과 선으로 이루어진 네트워크로, 뿌리로 알려진 하나의 출발점이다. $R$ 를 R $R$ 이라고 한다 $R$
플레이어는 각 단계에서 리프 $n$ $노드$ x $x$ 와 $x$ $자연$ 번호 n $n$ 을(를) 선택한다.leaf node는 루트가 아닌 한 줄만 연결된 점이다.
리프 $x$ $x$ 을(를) 제거하십시오 $x$ $a$ 을 $x$ 를) $x$ ${\displaystyle$ x $}$ 의 상위 항목으로 $a$ 두십시오. $a=R$ = $a=R$ ${\displaystyle a=R$ 2단계로 돌아가십시오.
$a\neq R$ $a\neq R$ $a\neq R$ 인 경우 $a\neq R$ $b$ $b$ 을(를) $a$ 의 부모로 $b$ 두십시오 $a$ $n$ ${\$ $displaystyle$ $n$ $}$ 을(를) 연결한 다른 모든 노드의 오른쪽에 있는 $b$ ${\$ $displaystystytype$ $b$ $}$ 에 $n$ 연결하십시오 $b$ 2 단계로 돌아가십시오.

유도는 플레이어가 항상 히드라를 죽일 것이라는 것을 증명하는 데 사용될 수 있다. $k$ $k$ 을(를) 뿌리와 잎 사이의 가장 큰 거리가 $k$ 되게 하라. $k=1$ = $k=1$ $k=1$ 인 경우 $k=1$ 잎을 제거하는 것은 아무런 효과가 없다: 히드라는 유한한 시간 내에 죽을 것이다. $k=m$ = $k=m$ $k=m$ 이 $k=m$ (가) 참이면 $k=m+1$ = m $k=m+1$ + $k=m+1$ $k=m+1$ 도 $k=m+1$ 참으로 한다.플레이어는 이제 $m$ 된 시간 동안만 m $m$ 이하의 $m$ 거리에서 나뭇잎을 계속 제거할 수 있다.잠시 후 플레이어는 리프 $m+1$ + $m+1$ {\ $displaystyle m+1$ }을 $m+1$ $($ 를) 떼어내야 한다. $m$ $m$ 만큼 $m$ 떨어진 잎이 없을 때까지 반복하십시오.그런 다음 다른 리프 $m+1$ + $m+1$ ${\displaystyle m+1$ }을 $m+1$ $($ 를) 제거하여 남은 항목이 없을 때까지 제거하십시오. $그러나$ 그때 모든 잎은 m $m$ 이하가 $m$ 된다.그 결과 어떤 유한한 히드라도 죽일 수 있다.

알고리즘을 개발할 수 있어가장 오른쪽 잎을 선택하고 $n=1$ = $n=1$ ${\displaystyle n=1$ }을 $($ 를) 처음 $n=1$ 설정하거나, $2$ $2$ 을(를) 두 번째 $2$ 설정하거나, 항상 $n$ $n$ 을(를) 하나씩 $n$ 증가시키십시오.히드라가 $단일$ y $y$ -길이 $y$ 분기를 가진 경우 $y=1$ = 1 $y=1$ 에 $y=1$ 히드라는 한 번에 죽임을 당하는 반면 y $y=2$ = $y=2$ ${\displaysty y=2$ }인 경우 세 단계로 죽임을 당한다 $y=2$ $y=3$ = $y=3$ $y=3$ 에는 11개의 단계가 필요하다 $y=3$ $y=4$ = $y=4$ $y=4$ 에 필요한 $y=5$ 의 단계가 있다 $y=5$ $y=5$ = 5 $y=5$ 이상에 $y=5$ 대한 단계의 양이나 이 함수의 증가율도 계산되지 않았다. 성장률이 급성장하는 계층 $f_{3}(n)$ 에서 f $f_{3}(n)$ 3 $($ {\ $displaystyf_{3}(n$ )보다 훨씬 클 가능성이 높다.

키르비-파리·부흐홀츠 하이드라스

커비-파리 히드라는 위에서 정의한 히드라의 네 번째 규칙을 변경함으로써 정의된다.

4_KP: $a\neq R$ $a\neq R$ $a\neq R$ 일 $a$ 경우 $b$ $b$ 이 $b$ $($ 가) ${\$ $displaystyle$ a}의 하위 $n$ 트리 복사본을 루트 a {\ $displaystyle$ a $}$ 과 $($ 와 $a$ $)$ $b$ $b$ 에 연결된 다른 모든 노드의 오른쪽에 $b$ 부착. $n$ 로 $b$ ^[2]

새 잎만 추가하는 대신 이 규칙은 전체 하위 트리의 중복을 추가한다.다른 모든 것을 동일하게 유지하면, $y=1$ 에는 y $y=1$ = 1 ${\displaystyle y=1$ }을 $y=1$ $1$ $($ 를) $1$ ${\displaystyle$ 1, $y$ = 2 $y=2$ y $=2}$ 을(를) $3$ ${\$ $displaystyle 3$ $}$ 스텝 $y=2$ $3$ , $y=3$ $y=4$ = $}$ 이 $y=3$ $37$ 37 $y=4$ {\ $displaystyty$ y= $4}$ 스텝이 Graham보다 더 많이 필요하다 $y=4$ . 번호를 매기다이 함수 증가율은 급속도로 성장하는 계층 구조에서 $f_{\varepsilon _{0}}(n)$ $f_{\varepsilon _{0}}(n)$ $f_{\varepsilon _{0}}(n)$ $f_{\varepsilon _{0}}(n)$ ( $f_{\varepsilon _{0}}(n)$ ) $f_{\varepsilon _{0}(n)$ 과 같은 거대하다.

이것은 가장 강력한 히드라가 아니다.부홀츠 하이드라는 더 강력한 ^[3]하이드라야라벨이 붙은 나무가 있다.루트에는 고유한 라벨( $R$ ${\displaystyle$ R $}$ 이라 함) $R$ 이 있으며, 각 노드에는 음이 아닌 정수 또는 $\omega$ ${\displaystyle \omega$ }인 라벨이 있다 $\omega$ ^[4]

히드라는 뿌리가 유한한 라벨이 붙은 나무다.루트에 $R$ $R$ 레이블을 붙여야 한다 $R$ 루트 $0$ ${\displaystyle 0}($ 항상 끝나는 것을 확인하는 데 중요함)에 인접한 모든 노드와 다른 모든 노드에 음이 $\omega$ 정수 또는 $Ω$ {\displaystyle $\omega }$ 을(으) 레이블을 붙인다 $\omega$
각 단계에서 $n$ 리프 노드 $x$ $x$ 과 $x$ (와) $n$ $n$ 을(를) 선택하십시오.
리프 $x$ $x$ 을(를) 제거하십시오 $x$ $a$ 을 $x$ 를) $x$ ${\displaystyle$ x $}$ 의 상위 항목으로 $a$ 두십시오. $a=R$ = $a=R$ ${\displaystyle a=R$ 2단계로 돌아가십시오.
$x$ ${\displaystyle x$ $}$ 의 레이블이 $x$ $0$ 인 경우 $,$ b {\ $displaystyle$ $}$ 이 $(가$ ) {\ $displaystyle$ $a}$ 의 상위 항목이라고 $b$ 가정하고 $a$ b ${\displaystyle$ $a}$ 루트를 사용하여 하위 $a$ 의 $n$ ${\$ displaystyle $b}$ 을 $n$ $a$ (으)에 연결된 다른 모든 노드의 $b$ 에 $b$ 연결하십시오. $b$ 2단계로 돌아가십시오.
x의 라벨이 $\omega$ ${\$ $displaystyle$ $\omega$ $}$ 인 경우 $\omega$ $n+1$ + $n+1$ 로 $교체$ 하십시오 $n+1$ 2단계로 돌아가십시오.
만약 x{\displaystyle)}의 라벨은 긍정적인 정수 니{\displaystyle u}. 라벨과 나무를 노드 c를 찾고 있{\displaystyle c}<>;{\displaystyle<>마}. 왜냐하면 모든 노드가 루트에 인접한 그러한 노드이다 레이블 0{0\displaystyle}존재한다. 루트 하위 트리의 사본을 뜨다. 줄어듭니다. c{ $\displaystyle c$ $이$ 하위 트리로 $x$ x $x$ 을(를) 교체하십시오.그러나 $u-1$ - $u-1$ ${\displaystyle$ $u-1$ $}$ 과(와) 함께 reelabel $x$ ${\displaystyle x}($ 하위 트리의 복사본 루트 $u-1$ 복사된 $하위$ 트리 x′ ${\$ $displaystyle$ x $'}$ 에서 $x$ $x$ ${\$ $displaystyty$ $x$ $}$ 과 동등한 이름을 $x$ 하십시오( $x'$ 그러므로 $x$ 는 $c$ ${\$ $di$ $}$ 에 $x'$ $c$ $).$ $splaystyle x})$ 및 reelabel $x$ $'$ ${\$ x $'}$ 0 $x'$ .2단계로 돌아가십시오.^[5]

놀랍게도, 비록 히드라가 엄청나게 자랄 수 있지만, 이 순서는 항상 끝난다.^[6]

KB 하이드라에 대해 자세히 알아보기

Kirby-Paris 하이드라의 경우 규칙은 간단하다: 주문되지 않은 뿌리 나무 $T$ $T$ 인 히드라로 시작한다 $T$ 각 단계에서 플레이어는 자를 잎 $c$ $노드$ c ${\displaystyle$ $c$ $}$ 와 음이 아닌 정수 $n$ ${\displaystyle$ n $}$ 을 선택한다 $n$ $만약$ c ${\$ $displays$ }이 $c$ 루트 $r$ 의자식이라면 $tyle r$ 그것은 나무에서 제거되고 그 다음엔 아무 일도 일어나지 않는다. $그렇지$ 않으면 p $p$ 을 $c$ 를) $c$ $c$ 의 상위 항목으로 $p$ 하고 $g$ $g$ 을 $p$ 를) $p$ $p$ 의 상위 항목으로 $g$ 한다.트리에서 $c$ $c$ $c$ 을(를) 제거한 다음 $n$ 된 $p$ $p$ 의 n $n$ 복사본을 $n$ $g$ $g$ 에 하위 항목으로 $p$ 추가하십시오 $g$ 히드라가 단일 노드로 줄어들면 게임은 끝난다.

빠르게 성장하는 기능을 얻기 위해서, $n$ 는 n{\ $displaystyle$ n $n$ 예를 $n=1$ $n=1$ = $n=1$ 1 {\ $displaystyle n=1$ }, $n=2$ n = $n=2$ 2 {\ $displaystyn$ $n=3$ $n=3$ = $n=3$ 3 {\ $displaystyn=3$ } $n=3$ 등을 수정하고, 항상 가장 오른쪽 잎을 선택하기 위한 간단한 규칙을 정할 수 있다.그런 다음 $\operatorname {Hydra} (k)$ style $\operatorname {Hydra} (k)$ ) $\operatorname {Hydra} (k)$ {\ $displaystyle \operatorname {Hydra}(k)}$ 은 $k$ 이 길이k {\ $displaystyle k$ $k$ $k+1$ k + $k+1$ 노드의 선형 스택으로 시작하는 데 필요한 단계 수입니다 $\operatorname {Hydra} (k)$ $.$ $\operatorname {Hydra} (k)$ $\operatorname {Hydra} (k)$ ( $\operatorname {Hydra} (k)$ ) $\operatorname {Hydra}(k)$ 은 $\operatorname {Hydra} (k)$ (는) 결국 Peano 산술에 총합한 모든 재귀 함수를 지배하며, 그 자체로 $\mathrm {PA} +(\varepsilon _{0}{\text{ is well-ordered}})$ + ( $\mathrm {PA} +(\varepsilon _{0}{\text{ is well-ordered}})$ ( $\mathrm {PA} +(\varepsilon _{0}{\text{ is well-ordered}})$ 은 $\mathrm {PA} +(\varepsilon _{0}{\text{ is well-ordered}})$ 가 잘 되어 있다 $\mathrm {PA} +(\varepsilon _{0}{\text{ is well-ordered}})$ ${\displaysty \mathrmatrm {PA}$ + $(\varpsilon _{0}{{{0}{{{{{{0$ ^[7]로

이는 대괄호 문자열을 사용하여 대신 표시할 수 있다.

$(()(()(())((()))))$ ( $(()(()(())((()))))$ ) $(()(()(())((()))))$ ( $(()(()(())((()))))$ ( $(()(()(())((()))))$ ) $(()(()(())((()))))$ ( ( $(()(()(())((()))))$ ) $(()(()(())((()))))$ ( ( $(()(()(())((()))))$ ) ) $(()(()(())((()))))$ ( $(()(()(())((()))))$ ) $(()(()(())((()))))$ ) ) $(()(()(())((()))))$ ) ) ( ) $(()(()(())((()))))$ ${\displaystyle$ ( $()($ ()()()()()()())})과 같은 괄호들의 유한 시퀀스로 시작하십시오 $(()(()(())((()))))$
빈 쌍 $()$ ) ${\displaystyle()}$ 과 $()$ (와) 음수가 아닌 정수 $n$ $n$ 을(를) 선택하십시오 $n$
쌍을 삭제하고 상위 쌍이 가장 바깥쪽 쌍이 아닌 경우 상위 쌍을 가져와서 해당 쌍의 $n$ $n$ {\ $displaystyle n}$ 복사본을 추가하십시오 $.$

For example, with $n=3$ , $(()(()\mathbf {()} ))\implies (()(())(())(())(()))$ . Next is a list of values of $\operatorname {Hydra} (k)$ :

$\operatorname {Hydra}(0)=0$
$\operatorname {Hydra}(1)=1$
$\operatorname {Hydra}(2)=3$
$\operatorname {Hydra}(3)=37$
$\operatorname {Hydra}(4)f_{\\omega \cdot 2+4}(5)\g {\text{Graham's number}}\company E[3]3\#\#4\#64$
$\operatorname {Hydra}(5)]f_{\omega ^{2+4}(5)$
$\operatorname {Hydra}(6)}f_{\underbrace {\omega ^{\cdots ^{\omega }} _{6}(5)$

Buchholz 하이드라에 대해 자세히 알아보기

Buchholz hydra 게임은 수학 논리에서의 히드라 게임으로, 수학 나무의 조각을 잘라내는 아이디어를 바탕으로 한 단일 플레이어 게임이다.히드라 게임은 빠르게 성장하는 함수 $BH(n)$ $BH(n)$ ( $){\displaystyle BH(n)}$ 를 생성하는데 사용될 수 있는데 $BH(n)$ 이것은 결국 모든 총 재귀 기능을 지배한다.커비-파리 수역의 연장선이다.What we use to obtain a fast-growing function is the same as Kirby-Paris hydras, but because Buchholz hydras grow not only in width but also in height, $BH(n)$ has a much greater growth rate of $f_{\psi _{0}(\varepsilon _{\Omega _{\omega }+1})}(n)$ :

$BH(1)=0$
$BH(2)=1$
$BH(3)<f_{\varepsilon_{0}}}\{0}(3)\관련 E[10]3\#\#3$

이 시스템은 무한정 서수(예: $\psi _{0}(\Omega _{\omega })=+0(\omega )$ 0 ( $\psi _{0}(\Omega _{\omega })=+0(\omega )$ ) $\psi _{0}(\Omega _{\omega })=+0(\omega )$ = $\psi _{0}(\Omega _{\omega })=+0(\omega )$ + 0 ( $\psi _{0}(\Omega _{\omega })=+0(\omega )$ ) $\psi _{0}(\Omega _{\omega })=+0(\omega )$ {\ $displaystyle \psi$ _ ${0}(\Oomega$ _ ${\omega }}}=+0(\omega$ )의 순서 표기법 생성에도 사용할 수 있다 $\psi _{0}(\Omega _{\omega })=+0(\omega )$

참고 항목

굿스타인의 정리

참조

^ Kirby, Laurie; Paris, Jeff. "Accessible independence results for Peano arithmetic" (PDF). Department of applied logic. Retrieved 2021-09-04.{{cite web}}: CS1 maint : url-status (링크)
^ "Hydras". agnijomaths.com. Retrieved 2021-09-05.
^ Hamano, Masahiro; Okada, Mitsuhiro (1995). "A Relationship among Gentzen's Proof-Reduction, Kirby-Paris) Hydra Game, and Buchholz's Hydra Game (Preliminary Report)*" (PDF). Research Institute for Mathematical Sciences, Kyoto University. Retrieved 2021-09-04.{{cite web}}: CS1 maint : url-status (링크)
^ Ketonen, Jussi; Solovay, Robert (1981). "Rapidly Growing Ramsey Functions". Annals of Mathematics. 113 (2): 267–314. doi:10.2307/2006985. ISSN 0003-486X. JSTOR 2006985.
^ Buchholz, Wilfried (1984-11-27). "An independence result for Π11 - CA + BI" (PDF). Ludwig-Maximilians-University of Munich. Retrieved 2021-09-04.{{cite web}}: CS1 maint : url-status (링크)
^ Hamano, Masahiro; Okada, Mitsuhiro (1998-03-01). "A direct independence proof of Buchholz's Hydra Game on finite labeled trees". Archive for Mathematical Logic. 37 (2): 67–89. doi:10.1007/s001530050084. ISSN 1432-0665. S2CID 40113368.
^ Carlucci, Lorenzo (2003-05-07). "A new proof-theoretic proof of the independence of Kirby–Paris' Hydra Theorem". Theoretical Computer Science. 300 (1–3): 365–378. doi:10.1016/S0304-3975(02)00332-8. ISSN 0304-3975.

이 글은 CCBY 4.0 면허에 따라 구할 수 있는 코미아미코의 문자를 통합한 것이다.

외부 링크

[1] Kirby, Laurie; Paris, Jeff. "Accessible independence results for Peano arithmetic" (PDF). Department of applied logic. Retrieved 2021-09-04.{{cite web}}: CS1 maint : url-status (링크)

[2] "Hydras". agnijomaths.com. Retrieved 2021-09-05.

[3] Hamano, Masahiro; Okada, Mitsuhiro (1995). "A Relationship among Gentzen's Proof-Reduction, Kirby-Paris) Hydra Game, and Buchholz's Hydra Game (Preliminary Report)*" (PDF). Research Institute for Mathematical Sciences, Kyoto University. Retrieved 2021-09-04.{{cite web}}: CS1 maint : url-status (링크)

[4] Ketonen, Jussi; Solovay, Robert (1981). "Rapidly Growing Ramsey Functions". Annals of Mathematics. 113 (2): 267–314. doi:10.2307/2006985. ISSN 0003-486X. JSTOR 2006985.

[5] Buchholz, Wilfried (1984-11-27). "An independence result for Π11 - CA + BI" (PDF). Ludwig-Maximilians-University of Munich. Retrieved 2021-09-04.{{cite web}}: CS1 maint : url-status (링크)

[6] Hamano, Masahiro; Okada, Mitsuhiro (1998-03-01). "A direct independence proof of Buchholz's Hydra Game on finite labeled trees". Archive for Mathematical Logic. 37 (2): 67–89. doi:10.1007/s001530050084. ISSN 1432-0665. S2CID 40113368.

[7] Carlucci, Lorenzo (2003-05-07). "A new proof-theoretic proof of the independence of Kirby–Paris' Hydra Theorem". Theoretical Computer Science. 300 (1–3): 365–378. doi:10.1016/S0304-3975(02)00332-8. ISSN 0304-3975.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Search