「計算可能関数」の版間の差分

計算可能関数は、[[自然数]]についての有限[[部分関数]]である。計算可能関数 <math>f</math> は引数として固定個の自然数をとり、個々の計算可能関数によって引数の個数は異なる。部分関数なので、あらゆる入力の組合せについて定義されているとは限らない。計算可能関数は出力として1つの自然数を返す（この出力を[[対関数]]を使って自然数のリストに変換することもできる）。<math> f(x_1,\ldots,x_k) \downarrow </math> と記した場合、引数 <math>x_1,\ldots,x_k</math> についての部分関数<math> f </math>を表し、<math>f(x_1,\ldots,x_k) \downarrow = y</math> と記した場合、<math>f</math> が引数 <math>x_1,\ldots,x_k</math> について定義されていて返す値が <math>y</math> であることを示している。これらの関数を'''部分再帰関数'''（Partial recursive function）と呼ぶ。再帰理論では、関数の定義域はその関数が定義されているあらゆる入力の集合とされる。