「計算可能関数」の版間の差分
削除された内容 追加された内容
→例: 誤訳修正+ビジービーバー関数を追加。参照：en:Computable function（版：12:34, 9 July 2009） |
m →例: typo |
||
73行目:
* πを計算した十進数列に ''n'' 個の連続した '5' が出現するなら ''f(n) = 1'' を返し、そうでなければ ''f(n) = 0'' を返すような関数 ''f'' は、計算可能である。（この関数は単に定数 1 を返すか、または、何らかの定数 ''k'' について、''n < k'' なら ''f(n) = 1'' を返し、''k ≤ n'' なら ''f(n) = 0'' を返す。このような関数は全て計算可能である。πの十進表現に '5' が任意の桁数連続して出現する場所があるかは不明なので、「どの」関数が ''f'' なのかを知ることは出来ない。けれども、どれが関数 ''f'' だろうとも、それが計算可能であることに変わりは無い訳である）
*自然数の計算「不能」な数列（例えば[[ビジービーバー#ビジービーバー関数
== チャーチ＝チューリングのテーゼ ==
| |||