計算可能
数論的関数
数論的関数
$ \Nは自然数全体の集合とする
$ f: \N^k \mapsto \Nを数論的関数と呼ぶ．
計算可能あるいはチューリングマシン計算可能
数論的関数$ f:\N^k\mapsto\Nが（チューリングマシン）計算可能であるとは以下と同値とする
次のTuringマシン$ \mathcal{M}が存在する
入力: $ 1^{m_1}01^{m_2}0\cdots01^{m_k}
出力: $ 1^{f(m_1,\dots,m_k)}
このとき$ \mathcal{M}は$ fを実現すると呼ぶ
例
以下は計算可能である．
加算$ +:\N^2\mapsto\N
乗算$ \times: \N^2 \mapsto \N
原始再帰的関数
定義
省略
系1