量子計算学習ノート - チューリング数1
この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。
ここではあらゆるチューリング機械の集合について議論しよう。この集合の性質を議論するためにチューリング機械に対するチューリング数という概念を導入したい。
最終的に示したいことは次のことだ。
チューリング機械は番号づけることができる。つまり、任意のチューリング機械は他のチューリング機械とは互いに異なる自然数で区別することができる。これはさらにいうと、チューリング機械の集合は可算無限であるということに他ならない
これが示せると、チューリング機械を入力としてその動作を再現するチューリング機械である「万能チューリング機械」というものを定義することができるようになる。
任意のチューリング機械を番号づけするためには「算術の基本定理」という自然数の性質が肝になる。今回はこの定理を証明して準備しておこう。
算術の基本定理は次のような定理だ。
自然数$${n \gt 1}$$の素因数分解は一意である
この定理を言い換えると、自然数とその素因数分解（可算無限次元の非負整数の組と考えられるだろう）は1:1対応する、ということになる。これにより、自然数を素因数分解に変換する写像には逆写像が存在するから、素因数分解が1つ与えられたら、それに対応する自然数がただ1つだけ定まるといえる。これがチューリング機械を番号づけする際に重要になる。
では証明していこう。まず、$${n \gt 1}$$なる自然数には素因数分解が可能であることを示す。
今、素因数分解不可能な$${1}$$より大きい自然数が存在すると仮定しよう。そのような集合を$${I \subset \mathbb{N}}$$とする。仮定より$${I \neq \phi}$$であるから、この集合には最小値$${\min I}$$が存在する。
素数はすでに素因数分解されているため、$${\min I}$$は合成数でなければならない。つまり適当な自然数$${a \gt 1,\ b \gt 1}$$を用いて$${\min I = ab}$$とかける。$${a, b \lt \min I}$$が成り立つから$${a, b \neq I}$$であり、$${a, b}$$は素因数分解可能であることが示される。すると$${\min I}$$も素因数分解されていることになり、仮定と矛盾する。
以上で、$${n \gt 1}$$なる任意の自然数は素因数分解可能であることが示された。次に一意性を示そう。
一意性は「ユークリッドの補題」と呼ばれる性質を示すことで証明することができる。「ユークリッドの補題」とは、「素数$${p}$$が自然数の積$${ab}$$を割り切るならば、$${p}$$は少なくとも$${a, b}$$のいずれか一方を割り切る」というものである。
ユークリッドの補題を示そう。まず素数$${p}$$が$${a}$$を割り切らないならば、$${p}$$と$${a}$$は互いに素であり、最大公約数は$${1}$$ということになる。実はこのことから$${px + ay = 1}$$なる整数$${x,y}$$の存在を示すことができる。これは「ベズーの等式」と呼ばれる。両辺を$${b}$$で掛けると$${pbx + aby = b}$$であり、$${ab}$$は$${p}$$で割り切ることから、$${p}$$は$${b}$$を割り切ることが示される。$${p}$$が$${b}$$を割り切らないとしたときも同様に、$${p}$$は$${a}$$を割り切ることが示せる。
補題中のベズーの等式は次のように示せる。
まず$${S \equiv \{px + ay: x, y \in \mathbb{Z}\}}$$と置こう。$${S}$$の正数のみを集めた集合を$${S_+}$$とすると、これは自然数の部分集合であるから最小値$${\min S_+}$$が存在する。$${S}$$の要素は実はこの最小値$${\min S_+}$$の倍数になっている。
実際、そうでない$${m \in S}$$が存在すると仮定してしまうと、$${m}$$を$${\min S_{+}}$$で割ったときの商を$${q}$$、余りを$${r}$$とすれば$${r = m - \min S_+ \cdot q}$$となる。簡単な計算で$${\min S_+ \cdot q \in S}$$であることが示せるから、$${r \in S_+}$$となる。$${r}$$は割り算の余りだから、$${\min S_+}$$よりも小さい。これは$${\min S_+}$$が$${S_+}$$の最小値であることに反する。
よって、任意の整数$${x, y}$$に対してある整数$${z}$$が存在して、$${px + ay = z \cdot \min S_+}$$と書ける。ここで$${x = 1, y=0}$$とおくと、$${p = z \cdot \min S_+}$$、$${x = 0, y = 1}$$とおくと、$${a = z' \cdot \min S_+}$$と書けることから、$${\min S_+}$$は$${p, a}$$の公約数である。$${p, a}$$の最大公約数を$${g ( = 1)}$$と置けば、$${\min S_+ \le g}$$が成立する。
また、$${p, a}$$はそれぞれが$${g}$$の倍数だから、$${p = p'g,\ a = a'g}$$と書け、任意の$${S}$$の元$${px + ay}$$にこれを代入すると、$${px + ay = g(p'x + a'y)}$$となる。つまり、$${S}$$の任意の元は$${g}$$の倍数であるから、適当な自然数$${n}$$を用いて$${\min S_+ = ng}$$。これは$${\min S_+ \ge g}$$を意味する。
以上より、$${\min S_+ = g}$$である。ゆえに$${p, a}$$の最大公約数$${g (=1)}$$を用いて、$${px + ay = g = 1}$$なる整数$${x, y}$$が存在することが示される。
さて、真に証明したい事柄に戻ろう。$${1}$$より大きい自然数の素因数分解の一意性について示す。
2通りの素因数分解が可能である自然数の存在を仮定しよう。そのような自然数の内、最小のものを$${n}$$とおき、これが素数$${p_1, p_2, \cdots, p_k, q_1, q_2, \cdots, q_l}$$を用いて
$$
n = p_1p_2 \cdots p_k = q_1q_2 \cdots q_l
$$
と書けたとする。$${p_1}$$は$${q_1q_2 \cdots q_l}$$を割り切るから、ユークリッドの補題により、$${p_1}$$に対して少なくとも$${j \in [1,l]}$$が存在し、$${q_j}$$を割り切る。つまり$${q_j = p_1 \cdot q'_j}$$となる。が$${q_j}$$はそもそも素数なので、$${q_j}$$もしくは$${1}$$でしか割り切れない。したがって$${q'_j = 1}$$である必要があり、$${q_j = p_1}$$が成立する。このとき全体を$${q_j = p_1}$$で割ると
$$
n' \equiv \frac{n}{p_1} = p_2 p_3 \cdots p_k = q_2 q_3 \cdots q_l
$$
と書ける。つまり$${n' \lt n}$$は2通りの素因数分解が可能となっているが、これは$${n}$$がそのようなものの最小であることに反する。
したがって、$${1}$$より大きい自然数の素因数分解は一意でなければならない。
この記事が気に入ったらサポートをしてみませんか？