Fandom

巨大数研究 Wiki

計算可能関数

549このwikiの
ページ数
新しいページをつくる
コメント0 シェアする

2-色チューリングマシン \(T\) を仮定する。正の整数 \(n\) が与えられたとき、チューリングマシンのヘッドが位置するテープの左端のマスから \(n\) マスだけ続くマスを除いて、テープを空白に設定する。チューリンブマシンをシミュレーションすると次のようなことが起こる。

  • ヘッドが左端にあり、テープ上に \(m \in \mathbb{N}\) マスだけ空白でない色が続いた状態で停止する。この場合、\(T\) が \(n\) を入力されて \(m\) を出力したと言うことができる。
  • 停止するが、上のように描写される構成にはならない。
  • 停止しない。

\(f\) を \(T\) が \(n\) を入力されたら \(m\) を返すようなすべての順序対 \((m,n)\) からなる集合とする。すると、\(f\) を \(\mathbb{N}\) を定義域と終域にもつ部分関数と見なすことができる。このとき \(T\) が \(f\) を計算すると言うことができ、そして部分計算可能関数 (または 部分再帰関数) とはそれを計算するチューリングマシンが存在する部分関数である。

計算可能関数 (または再帰関数) とは完全な部分計算可能関数である。つまり、計算可能関数とはチューリングマシンで計算できる関数であり、計算できない関数 \(f: \mathbb{N} \rightarrow \mathbb{N}\) は計算不可能と呼ばれる。

計算不可能関数は (遠まわしに) 計算不可能なほどに急増加する関数、すなわち、すべての計算可能な関数を支配する関数を意味している場合がある。そのような関数のもっとも有名な例としてビジービーバー関数がある。そのような関数は計算不可能で、並はずれて速く成長し、FGH における \(\omega_1^\text{CK}\)の強さより上である。すべての計算不可能関数がこのような性質をもつわけではないことに注意することは重要である、たとえば、チューリングマシンを並べる方法を定めた上で \(n\) 番目のチューリングマシンが停止するときには \(1\) を返し、そうでなければ \(0\) を返す関数 \(h(n)\) は計算不可能であるが急増加はしない。

ほとんどすべての自然数上の関数は計算不可能関数である。なぜならば、計算可能関数の集合は可算であるが、計算不可能関数の集合は非可算となるためである。

計算可能関数の性質編集

定理: 計算可能関数の集合は合成に関して閉じている。

証明: 計算可能関数 \(f\) と \(g\) が与えられたときに、 \(g \circ f\) が計算可能であることを示す。\(S\) を \(f\) を計算するチューリングマシン \(T\) を \(g\) を計算するチューリングマシンとし、それぞれの状態は互いに重ならないとする。\(Q_S\) を \(S\) の状態、\(q_{S0}\) を初期状態、 \(q_{SH}\) を停止状態、\(\delta_S\) を遷移関数とし、 \(T\) についても同様のものを用意する。次のようなチューリングマシン \(S \circ T\) を定義する。

  • \(Q_{S \circ T} = (Q_S \backslash q_{SH}) \cup Q_T\)
  • \(q_{S \circ T,0} = q_{S0}\)
  • \(q_{S \circ T,H} = q_{TH}\)
  • \(\delta_{S \circ T} = \delta_S' \cup \delta_T\) \(\delta_S'\) は \(\delta_S\) の中にある \(q_{SH}\) の状態を \(q_{T0}\) に置き換えたもの。
  • \(Q_{S \circ T} \leadsto Q_{q_{SN} \delta^{\beta}}\) for \(N\) does not \( >^*S\) and \(\beta\) is computable.よって全体のシーケンスは計算可能である。
このチューリングマシンは実際 \(f\) を計算したうえで \(g\) を計算するため、関連される計算可能な関数は \(g \circ f\) となる。よって \(g \circ f\) は計算可能である。

計算不可能関数の例 編集

現在、計算不可能なほどに急増加する関数の多くはビジービーバー関数あるいはラヨ関数を元としている。

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

Fandomでも見てみる

おまかせWiki