コンウェイのチェーン表記の基本
コンウェイのチェーン表記の基本
\(a,b,c\)は正の整数、\(X\)は部分チェーンとする。
\(a,b,c\)は正の整数、\(X\)は部分チェーンとする。
(1)
\[ a\rightarrow b\rightarrow0=ab \](2)
\[ a\rightarrow0\rightarrow b=1-\delta_{0b} \](3)
\[ X\rightarrow a\rightarrow b=X\rightarrow c \](4)
\[ a\rightarrow X=a^{b} \](5)
\[ 1\rightarrow X=1 \](6)
\[ X\rightarrow1\rightarrow Y=X \](7)
\[ 2\rightarrow2\rightarrow X=4 \](8)
\[ X\rightarrow2\rightarrow2=X\rightarrow\left(X\right) \](9)
\[ a+b=a\rightarrow b\rightarrow\left(-1\right) \](10)
\[ \frac{a}{b}=a\rightarrow\left(b\rightarrow\left(-1\right)\right)\rightarrow0 \](11)
\[ a\rightarrow n\rightarrow2=\log_{a}H_{4}\left(a,n+1\right) \](12)
\[ a\rightarrow\left(-1\right)\rightarrow2=0 \]-
\(\rightarrow\)はコンウェイのチェーン表記(1)
\begin{align*} a\rightarrow b\rightarrow0 & =a\uparrow^{0}b\\ & =ab \end{align*}(2)
\begin{align*} a\rightarrow0\rightarrow b & =a\uparrow^{b}0\\ & =1-\delta_{0b} \end{align*}(3)
\[ X\rightarrow a\rightarrow b=X\rightarrow\left\{ X\rightarrow\left(a-1\right)\rightarrow b\right\} \rightarrow b-1 \] なので、これを繰り返すと、右端が1となりチェーンが1短くなる、または右側から2番目の数字が1になりそれ以降の数字が消せるので、\[ X\rightarrow a\rightarrow b=X\rightarrow c \] となる正の整数が存在する。
(4)
\(X\)が長さ0のチェーンの場合は1となるので、\(a\rightarrow X=a\)となる。\(X\)が長さ1のチェーンの場合は正の整数\(b\)となるので、\(a\rightarrow X=a^{b}\)となる。
\(X\)が長さ2以上のチェーンの場合は長さ1以上のチェーン\(Y\)を用いて\(a\rightarrow X=a\rightarrow p\rightarrow Y=a\rightarrow p\rightarrow q=a\uparrow^{q}p=a^{b}\)となる。
これより、任意の\(X\)のチェーンの長さに対して\(a\rightarrow X=a^{b}\)が成り立つ。
(5)
(4)で\(a=1\)とすればいい。(6)
\(Y\)が長さ0のチェーンの場合は1となるので、\(X\rightarrow1\rightarrow Y=X\)となる。\(Y\)が長さ1のチェーンの場合は\(X\rightarrow1\rightarrow Y=X\rightarrow1\rightarrow a=X\)となる。
\(Y\)が長さ2以上のチェーンの場合は\(X\rightarrow1\rightarrow Y=X\rightarrow1\rightarrow a=X\)となる。
これより、任意の\(X\)のチェーンの長さに対して\(X\rightarrow1\rightarrow Y=X\)が成り立つ。
(7)
\begin{align*} 2\rightarrow2\rightarrow X & =2\rightarrow2\rightarrow a\\ & =2\uparrow^{a}2\\ & =4 \end{align*}(8)
\begin{align*} X\rightarrow2\rightarrow2 & =X\rightarrow\left(X\rightarrow1\rightarrow2\right)\rightarrow1\\ & =X\rightarrow\left(X\right) \end{align*}(9)
\begin{align*} a+b & =a\uparrow^{-1}b\\ & =a\rightarrow b\rightarrow\left(-1\right) \end{align*}(9)-2
\begin{align*} ac & =a\rightarrow c\rightarrow0\\ & =a\rightarrow\left(a\rightarrow\left(c-1\right)\rightarrow0\right)\rightarrow\left(-1\right)\\ & =a\rightarrow\left(a\left(c-1\right)\right)\rightarrow\left(-1\right) \end{align*} となるので、\(\left(a\left(c-1\right)\right)=b\)とおくと\(c=\frac{b}{a}+1\)となり、\begin{align*} a\rightarrow b\rightarrow\left(-1\right) & =a\left(\frac{b}{a}+1\right)\\ & =a+b \end{align*} となるので、与式は成り立つ。
(10)
\begin{align*} \frac{a}{b} & =a\uparrow b^{-1}\\ & =a\rightarrow b^{-1}\rightarrow0\\ & =a\rightarrow\left(b\rightarrow\left(-1\right)\right)\rightarrow0 \end{align*}(11)
\begin{align*} a\rightarrow n\rightarrow2 & =H_{4}\left(a,n\right)\\ & =\log_{a}a^{a\uparrow^{2}n}\\ & =\log_{a}\left(a\uparrow a\uparrow^{2}n\right)\\ & =\log_{a}\left(a\uparrow^{2}\left(n+1\right)\right)\\ & =\log_{a}H_{4}\left(a,n+1\right) \end{align*}(12)
\begin{align*} a\rightarrow\left(-1\right)\rightarrow2 & =H_{4}\left(a,-1\right)\\ & =\log H_{4}\left(a,0\right)\\ & =\log1\\ & =0 \end{align*}(12)-2
\begin{align*} a\rightarrow\left(-1\right)\rightarrow2 & =\log_{a}\left\{ a\rightarrow\left(a\rightarrow\left(-1\right)\rightarrow2\right)\rightarrow1\right\} \\ & =\log_{a}\left(a\rightarrow0\rightarrow2\right)\\ & =\log_{a}\left(1-\delta_{02}\right)\\ & =0 \end{align*}ページ情報
タイトル | コンウェイのチェーン表記の基本 |
URL | https://www.nomuramath.com/fc44e4iz/ |
SNSボタン |
ハイバー演算子の定義
\[
H_{n}\left(a,b\right):=\begin{cases}
b+1 & n=0\\
a+b & n=1\\
\underbrace{a^{\left(n-1\right)}a^{\left(n-1\right)}\cdots a^{\left(n-1\right)}a}_{b\;copies\;of\;a} & n=2,3,\cdots
\end{cases}
\]
ハイバー演算子の基本的な値
\[
H_{n}\left(0,a\right)=\begin{cases}
a+1 & n=0\\
a & n=1\\
0 & n=2\\
\delta_{0a} & n=3\\
\delta_{0,\mod\left(a,2\right)} & n=4,5,\cdots
\end{cases}
\]
クヌースの矢印表記の定義
\[
a\uparrow^{n}b:=\begin{cases}
ab & n=0\\
1 & n\geq1\;\land\;b=0\\
\underbrace{a\uparrow^{n-1}a\uparrow^{n-1}\cdots\uparrow^{n-1}a}_{b\;copies\;of\;a} & otherwise
\end{cases}
\]
コンウェイのチェーン表記の優先順位
\begin{align*}
& a\rightarrow\left(b\rightarrow c\right)\\
& a\rightarrow b\rightarrow c\\
& \left(a\rightarrow b\right)\rightarrow c
\end{align*}