計算可能関数

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} \mapsto \mathbb{N}\) は計算不可能と呼ばれる。

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

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

計算可能関数の性質

Theorem: The set of computable functions is closed under composition.

Proof: Given computable \(f\) and \(g\), we wish to show that \(g \circ f\) is computable. Let \(S\) be a Turing machine that computes \(f\), and \(T\) a Turing machine that computes \(g\), such that the states of \(S\) and \(T\) are disjoint. Let \(Q_S\) be the states of \(S\), Let \(q_{S0}\) be the initial state, let \(q_{SH}\) be the halting state, let \(\delta_S\) be the transition function, and like so for \(T\). Then define the Turing machine \(S \circ T\) like so:

• \(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\) where \(\delta_S'\) replaces all instances of \(q_{SH}\) in \(\delta_S\) with \(q_{T0}\).
• \(Q_{S \circ T} \leadsto Q_{q_{SN} \delta^{\beta}}\) for \(N\) does not \( >^*S\) and \(\beta\) is computable.Thus the whole sequence is computable.

Since this Turing machine effectively computes \(f\) and then \(g\), its associated computable function is \(g \circ f\). Therefore \(g \circ f\) is computable.

∎

Notable uncomputable functions

Currently, most uncomputably fast-growing functions are derived from the busy beaver or the Rayo function.

• Busy beaver function
• Doodle function
• Xi function
• Rayo's function
• FOOT function