|| 計算できるかどうかとか効率的かどうかとか
『人間に扱えるか』についてあれこれ調べた成果。
スポンサーリンク
「人間に扱えるか」の指標として
これは「小さな自然数」と密接に関係しています。
目次
・計算可能性「答えが出せるかどうか」
チャーチ=チューリングのテーゼ「計算可能性の定義」
計算可能関数「計算可能性を定義するもの」
帰納的・再帰関数「計算可能性の定義に使われる関数」
ラムダ計算「1引数1出力の単純な関数」
原子再帰関数「再帰関数の厳密な定義」
・チューリングマシン「一番いろんなものを計算できる機械」
神託機械「マシンの停止問題を解消するための機械」
停止性問題「ループするか絶対に分かるプログラムは無い」
・主要な性質
実効性「証明の妥当性を確認する方法があるという性質」
決定可能性「論理式がその元の理論のものか確認できる性質」
決定問題「あらゆるものの是非を決めるために作られる」
・計算複雑性「主にどれくらいの時間で計算できるかとか」
チューリング次数「計算の複雑さを表す指標」
・再帰定理「全部自分でいけるよ、みたいな話」
なんじゃこれはと初見では思いましたが、
実はこれ、非常に重要な考え方で、
例えば「形式言語」（プログラムなど）は
これを基軸として作られていたり
「効率化」を考える上で
大まかな指標を提供してくれたり
わりと実践的な計算をする場合
この理論の考え方が使われたりします。
具体的には、
例えば「無限」に処理が続いてしまって
「答えが出ない」ものに価値はありませんよね。
これはまあ要はそういう話で、
なにか「明確な価値」あるものは、
「有限」の処理で「答えが出る」ものに限られる。
再帰理論はこの事実の根拠になっていて、
だからこそ「計算可能性」やら「計算複雑性」やら
そういうのを主に扱うことになっています。
計算可能性理論 Computability Theory
|| 計算できるってどういうことなの？
「計算できる」ってなに？ を突き詰めた成果
この理論の主な成果は
この疑問に関連するものになります。
「再帰理論」っていうより
こっちで呼んだ方が意味は分かり易いかも。
実際、こっちで呼ぶべきだって人は一定数いるみたいですね。
主要な研究対象は
「計算可能関数」と
「計算可能」な「クラスが持つ構造」について
後者は「クラス」「構造」が分からんと思いますが
「計算可能関数」はなんとなく分かるかも？
使われるとこ
これは「計算機科学」にそのまま使われています。
ハードの基礎・ソフトの基礎はだいたいこれです。
他にも
『これ答え出せるんかいな？』っていうのとか
『答えを出すにはどうすれば？』っていうのとか
こういうのを突き詰めると
だいたいこの理論に行き着きます。
計算可能性
「計算可能性」は「定義」になります。
「定理」として「証明されたもの」ではありません。
いわば『妥当性が認められた人間の作ったルール』です。
↓ の「提案」が採用されて、初めて明確に定義されました。
チャーチのテーゼ Church’s Thesis
|| 計算可能をこう定義しよう
「計算できる関数」と「帰納的関数」は同じ
『そういうことにしない？』っていう提案
『再帰理論』における核の一つです。
これにより、計算可能性は明確に定義されました。
余談になりますが、
これは「非形式」を「形式化」した貴重な一例でもあります。
それと「チャーチ」ですが、これは人名で、
フルネームは「チャーチ = チューリング」
そこからとって、
これは「チャーチ = チューリングのテーゼ」とも呼ばれます。
計算できる
『実際に計算する方法（計算機の機能）』から
「計算できる」は定義されています。
ここで採用される『計算機』は
だいたい「チューリングマシン」ですね。
この「チューリングマシン」という仮想機械
その『機能』で「実現可能であるか」
それによって「計算可能であるか」は判別されます。
まあつまり
この「計算機で計算できない」ものは
当然「計算可能」ではありません。
計算可能関数 Computable Function
|| 意味は分かっても中身が分からん
「答えが確実に出る関数」のこと。
これは「答えが出せるアルゴリズムが存在する」なら
確実に存在します。
逆に「アルゴリズムが無い」場合
「計算可能関数」は定義することができません。
ちなみにこの中身が「帰納的関数・再帰関数」になります。
帰納的・再帰関数 Recursive Function
|| 計算できるやつとして名指しされたやつ
『有限個の自然数』から『1つの自然数』を得る
そういう『変数 → 1 つの自然数』になる関数のこと。
\begin{array}{lllll} \displaystyle n_1,n_2,...,n_p,n_c&∈&N \end{array}
\begin{array}{lllllllllll} \displaystyle f_{\mathrm{recursive}}(n_1,n_2,...,n_p)&=&n_c \end{array}
まあ要は「いつも使ってる関数」のことで、
例えば「 5+3=8,\,\,\,2*3=6 」とかはこれ。
というか知られてる演算はほぼこれですね。
ちなみに
「帰納的関数」と「再帰関数」は同じものだと思ってOKです。
「帰納的」も「再帰的」も英訳は（ \mathrm{Recursive} ）ですし。
実数じゃなく自然数
なんで『実数を使わないのか』って話ですが、
これは「人間・機械では正確に扱えないから」
っていうのが主な理由になります。
というのも、
「自然数」は『有限個の資源で正確に表現できる』のに対し、
「実数」は『有限個の資源で正確に表現できる』とは限りません。
もちろん理論上であれば、
実数を使った計算は可能です。
\begin{array}{lllllll} \displaystyle \sqrt{2}\sqrt{2}&=&2 \\ \\ \sqrt{2}&=&1.4142135623.... \end{array}
しかし「実数」を『正確に表現しようとする』と
無限桁を表現しなければならず
となれば、それを実現するには
「記憶するためのスペース」を無限個用意する必要があって、
しかし実際には、無限個用意することはできません。
最小の部品が磁気でバイナリを記録する今の計算機では、
スペースは『有限個』しか用意することができないんです。
\begin{array}{lllll} \displaystyle \sqrt{2}&=&1.41421356... \\ \\ \displaystyle \sqrt{2}&≒&1.41421356 \end{array}
まあだから実数は使わず自然数が使われ、
実数は有理数へと変換され計算されることになっている。
だから実数は使わない、というか使えないんですね。
ラムダ計算 Lambda Calculus
|| ラムダ（意味不明）計算（これは分かる）
『決まった手順』での「計算の実現方法」の『雛型』
これの「引数」「出力」は『一つだけ』です。
\begin{array}{rlllllll} \displaystyle f(x)&=&x+1 \\ \\ λx&.&x+1 \end{array}
\begin{array}{rllllllll} \displaystyle f(3)&=&3+1 \\ \\ (λx&.&x+1)&3 \end{array}
\begin{array}{llllll} \displaystyle (λf&.&f&3)&(λx&.&x+1) \\ \\ &&&&(λx&.&x+1)&3 \\ \\ &&&& && 3+1 \end{array}
\begin{array}{rllllllll} \displaystyle f(x,y)&=&x+y \\ \\ λx&.&(λy.x+y) \end{array}
\begin{array}{llllllll} \displaystyle λx&.&(λy&.&x+y)&2&3 \\ \\ &&(λy&.&2+y)&3 \\ \\ &&&& 2+3 && \end{array}
「計算可能な関数 F : N→N 」
これを定義するときに使われたりしますが
\begin{array}{lclll} \displaystyle F(X)&=&Y \\ \\ fx &==&y \end{array}
それより「プログラムの表現方法」的な話とか
そういうので出てくることが多いですね。
詳細は「不動点コンビネータ」とかの話になるので
この辺りは別の記事で扱うことにします。
ちなみに「 λ 」自体には特に意味はありません。
よくこう書かれるからラムダ計算って呼ばれてるだけです。
\begin{array}{lllllll} \displaystyle λx.λy.x+y \\ \\ λxy.x+y \end{array}
それと多変数を表記する時に使われる
こんな感じの省略された表現もあります。
原子再帰関数 Primitive Recursive
|| 再帰関数の基本みたいなもの
「基本的な関数の性質を持つ」関数のこと
再帰関数ですから
「定義域・始域」「像・終域」は『自然数』になります。
以下、原子再帰関数は 3+2 個の制約によって
その中身を厳密に定義されています。
・ 0 項の「定数関数」は原子再帰関数である
・ 1 項の「後者関数」は原子再帰関数である
・ n 項の「射影関数」は原子再帰関数である
・有限個の原子再帰関数の「合成関数」は原子再帰関数である
・「原子再帰法で得られた関数」は原子再帰関数である
「定数関数 \mathrm{Constant \,\, Function} 」ですが
これは要は「定数（ 0,1,2,a とか）」のことですね。
「後者関数 \mathrm{Successor \,\,Function} 」は
「 \mathrm{Suc}(x)=x+1 」みたいなやつのことで、
『次』みたいなものを定義する時に使われたりします。
「射影関数 \mathrm{Projection \,\, Function} 」については
これはつまり「多変数関数 f(x,y) 」の話で、
\begin{array}{lllllllllll} \displaystyle f(x,y,z)&=&g\Bigl(h_1(x,y),h_2(y,z) \Bigr) \\ \\ f(x,y,z)&=&g\Bigl( h_1 \Bigl( P_{1}^{3}(x,y,z),P_{2}^{3}(x,y,z) \Bigr) ,h_2\Bigl( P_{2}^{3}(x,y,z),P_{3}^{3}(x,y,z) \Bigr) \Bigr) \end{array}
こういう操作を考える時に必要に。
少々複雑ですが、これはわりと不可欠な操作になります。
ちなみに「射影関数 P_{3}^{2}(x,y,z) 」の記号は
この場合「 3 項」の中から 2 番目の引数を選択
つまり P_{3}^{2}(x,y,z)=y となることを意味します。
「合成 \mathrm{Composition} 」はそのままですね。
「合成関数」 f \Bigl( g(x) \Bigr) , f \Bigl( g_1(x,y), g_2(x,y) \Bigr)
こういう操作を許容します。
\begin{array}{llllll} \displaystyle f_{\mathrm{Composition}}(x_1,...x_n)&=&f\Bigl( g_1(x_1,...x_n),...,g_k(x_1,...,x_n) \Bigr) \end{array}
一般形はこんな感じ。
ややこしいですね。
最後「原子再帰法 \mathrm{Primitive \,\, Recursion} 」ですが
「再帰関数」の『再帰的処理』を許容します。
\begin{array}{lllllll} \displaystyle \mathrm{add}(0,x)&=&x \\ \\ \mathrm{add}(n+1,x)&=&\mathrm{add}(n,x)+1 \\ \\ \\ \mathrm{add}(2,x)&=&\mathrm{add}(1,x)+1 \\ \\ &=&\mathrm{add}(0,x)+1+1 \\ \\ &=&x+1+1 \end{array}
代表的な例だとこういう「加算」の関数とか
こういうのを原子再帰関数として認めます。
\begin{array}{llllll} \displaystyle \mathrm{Func}(0,x_1,...,x_n)&=&f(x_1,...x_n) \\ \\ \mathrm{Func}(n+1,x_1,...,x_n)&=&g(\mathrm{Func}(n,x_1,...,x_n),n,x_1,...,x_n) \end{array}
一般形はこんな感じ
形は複雑ですが言ってることは単純です。
チューリングマシン Turing Machine
|| ゲームとかで聞くやつ
一番良い感じの「計算機（コンピュータ）」のこと。
「計算機」を「数学的に扱う」ために考えられたもので
「仮想機械」なんて言われたりもします。
役割
これはあらゆる「計算機」の中で
現在「最も現実的」であり「いろいろ計算可能」
まあつまり『現実的な万能性』を持っています。
でまあそんなわけですから、
「仮想機械」っていったら大体これのことを指していて
『ほとんどすべての計算ができる』上で
『現実的なもの』はだいたいこれの派生形になります。
具体的には
『物理的な実体』になる「ハードウェア」とか
そういうのを作る上でこの考え方は便利で、
私たちが利用するほぼ全ての計算機は
基本、このチューリングマシンの構造を持っています。
神託機械 Oracle Machine
|| 困ったときのなんとやら
「停止問題」を解決する手段の一つ。
「神託」ですから、
これはまあ要は神頼みのことで、
「決定不能な問題」なんかに対して
なんらかの値を無理矢理割り当てることで、
これは無限に続いてしまうような計算に解答を用意します。
「チューリングマシンの停止問題」なんかで見る話ですね。
答えが出ない問題を解く時とかの話でよく見ます。
停止性問題 Halting Problem
|| 有限時間で計算できる？を確認することは可能であるか
「停止しないかどうか」を『有限時間』では確認できない
これもまた再帰理論の核の一つと呼べるもので、
既に確認されている成果の１つになります。
証明
使うのは背理法です。
判定したいプログラムを f とし、
停止性問題を解くプログラム \mathrm{Halt} が存在すると仮定して
\begin{array}{lllllllll} \mathrm{Halt}(f)&=&\left\{ \begin{array}{lllllll} \mathrm{True} && f &\mathrm{does} \,\, \mathrm{not}&\mathrm{loop} \,\, \mathrm{infinitely} \\ \\ \mathrm{False} && f & & \mathrm{loops} \,\, \mathrm{infinitely} \end{array} \right.\end{array}
↑ のようなプログラムを考えることで矛盾を導きます。
そのために
「停止しない → 停止させる」
「停止する → 停止させない」
\begin{array}{llllllllll} \displaystyle G&=&\left\{ \begin{array}{lllll} \displaystyle G &&\mathrm{if} &\mathrm{Halt}(G) = \mathrm{True} \\ \\ \mathrm{True} &&\mathrm{if} &\mathrm{Halt}(G) = \mathrm{False} \end{array} \right. \end{array}
そういうプログラム G を考えて
\begin{array}{lllllllllllllllll} G \,\, \mathrm{loops} \\ \\ \displaystyle \mathrm{Halt}(G) = \mathrm{False} &→&\mathrm{True}& &&\mathrm{don't \,\,loop?} \\ \\ \\ G \,\, \mathrm{doesn't \,\,loop} \\ \\ \mathrm{Halt}(G) = \mathrm{True}&→&G&\cdots &&\mathrm{loop?} \end{array}
それぞれ整理していくとこうなりますから、
いずれのパターンにおいても矛盾が出る
ということは、すなわち「仮定」が間違っている
\begin{array}{lllllllll} \mathrm{Halt}(f)&=&\left\{ \begin{array}{lllllll} \mathrm{True} && f &\mathrm{does} \,\, \mathrm{not}&\mathrm{loop} \,\, \mathrm{infinitely} \\ \\ \mathrm{False} && f & & \mathrm{loops} \,\, \mathrm{infinitely} \end{array} \right.\end{array}
まあつまり『判定不可能な G が存在する』以上
この \mathrm{Halt} の存在を仮定すると矛盾を導くので
「判定できる（仮定）」→「矛盾が生じる」ことから、
『停止性問題を解くプログラム』は存在しない、と言えます。
実効性 Effective
|| 聞くようで意味はよく分からない単語
（そういう検証できるアルゴリズムが存在する）
この性質が保証される場合
「答えが出ること」が保証されます。
しかし当然ですが、それ以外のことは保証しません。
なので「計算複雑性理論」で語られる
「効率性 \mathrm{Efficient} 」とかの話には無関与です。
それと補足しておくと、
これは『全ての定理』が満たすとは限りません。
『全て』という量化処理が関わる場合、
「無限個」のものを想定する必要があったりするので。
（ファルティングスの定理など）
決定可能性 Decidable
|| 現実的に決まるかどうか
そのまま「決定できるかどうか」の話で、
その『手順が有限である』ことなんかが条件に来ます。
まあつまり「実効性」をベースにしたもので
「論理式」がその『理論の中にある』と
「実効的」に「確認する方法」がある
これが満たされるとき、
それに対して『決定可能』と言います。
イメージし辛いかもしれませんが
要は「このルールで分かる」って話で、
例えば「ある論理式・式・値」が与えられた時、
それの『所属を判別するプログラムがある』なら
その『所属先を判定可能な集合』の
その中にある論理式を含めて「決定可能」って言う感じで
まあつまり比較すると ↓ みたいな感じ。
「実効性」は『論理式の正しさ』を有限の範囲で判定できる性質
「決定可能性」は『ある理論の論理式である』ことを判定できる性質
数学的な関連
「決定可能な理論」の中で最も有名な例は
論理演算として代表的な「命題論理」です。
ここでその詳しい証明はしませんが、
「命題論理」にはその「論理式」が
「命題論理のものであるか」を確認する方法があって
具体的には「真理値の確認」ができるので、
これによりその「論理式」が「定理」かどうか確認できる
だから結果として
「定理」なら「命題論理」に含まれる、と言えます。
まあつまり「実効的」に帰属先を確認できることから、
「真理値が確認できる」なら「命題論理の論理式」
こういう形で『判定する手順を作れる』
だから「命題論理の論理式」なら
それは「決定可能性を持つ」と言えるわけです。
ちなみに『一階述語論理』の場合は、
それで話が変わります。
というのも『一階述語論理』は、
「一般的（なんでも）」には
「決定可能」だとは言えないんですよ。
採用する『非論理記号』が
「等号」以外には「アリティ 1 」の記号だけ
こういう場合に限るのなら
『一階述語論理』は「決定可能」であると言えますが
量化子である『全て』などが絡む場合、
範囲を拡大すると実効性を保証できなくなったりします。
決定問題 Decision Problem
|| 名前のわりに大事なもの
「はい」か「いいえ」を返す『問題』のこと。
\begin{array}{llllllll} \displaystyle f&:&\{0,1\}^n&→&\{0,1\} \end{array}
ありとあらゆる問題は
突き詰めれば 2 択（はい・いいえ）にできるので
問題を単純化すると最終的にここに行き着きます。
\begin{array}{lllllll} \displaystyle あ&:=&0010001000100100 \end{array}
「 \{0,1\}^n 」の中身は ↑ みたいなやつです。
計算複雑性 Computational Complexity
|| 複雑な計算ってなんで複雑なんだろ
これは「最適化」「効率化」なんかを扱う分野です。
「計算量」やら「計算の複雑さ」やら
そういうのがこの分野で主に扱われるものになります。
代表的な活用例は『暗号理論』とかですね。
『現実的に解読不可能』である
これを定める基準に使われたりします。
具体的な感じ
計算は「何もない状態」で行えるものではありません。
「目的」「必要な時間」「記憶領域」「演算の方法」
こういったものは最低限必要で、
これらが無ければ計算自体起きることがありません。
なのでこの辺りのことを知り、定めることは、
数学において必須とも言える行為と言えます。
複雑さと無限性
「時間」は「無限」にあるわけではありません。
「記憶領域（メモリ）」も「無限」ではないですし
「演算速度」も「無限速」ではないです。
ですから、
もし仮に「ほぼ無限」に資源が必要になるなら
例えば「計算可能」ではあるけれど
計算が終わるには 1000 兆年くらい掛かるよ、みたいな
そういう規模の時間が必要な場合、
それは『現実的には答えを出せない』ことになります。
（RSA暗号とか 将棋の最善手とか）
複雑性が重要になるのはこれが理由で、
「計算可能」であることと
『現実的に答えを出せるか』はこの点で差別化されます。
以上、この分野はこんな感じ。
「 P=NP 問題」とかを扱ったります。
詳細は別の記事『計算複雑性理論』で。
チューリング次数 Turing Degree
|| 複雑さを表す指標が欲しい
「複雑さ」を示す「同値類」のこと。
\begin{array}{lllllll} \displaystyle \textbf{0}≤_{T}X≤_{T}Y \end{array}
基本は「自然数」ベースですが、
この話はちょっとややこしいです。
チューリング還元
「問題 B が簡単に解ける（仮定）」→「問題 A が簡単に解ける」
「問題 A は問題 B にチューリング還元される」
「 A は B にチューリング還元可能である」
\begin{array}{llllllll} \displaystyle A&≤_{T}&B \end{array}
これはまあこんな感じの話で、
これが満たされる時
「問題 B を解けるあらゆるプログラム」は
「問題 A を解くプログラム」これの作成に使える
こういうことを意味します。
A は「 B – 帰納的」「 B – 計算可能」なんて言うことも。
より一般的かつ厳密には
「問題 B についての神託を与えられた神託機械」
これを使えば「問題 A の特性関数は計算可能である」
\begin{array}{llllllll} \displaystyle A&≤_{T}&B \end{array}
って感じですが、
こっちはまあよく分からんですね。
具体的には、例えば「足し算」で考えるなら、
\begin{array}{llllllllll} \displaystyle \mathrm{add}(x)&=&x+1 \\ \\ \mathrm{add}(x,y)&=&x+y \end{array}
まあこんな感じで、
「 \mathrm{add}(x) 」は「 \mathrm{add}(x,y) 」で解けるよ
って感じの話でしかないんですが。
チューリング同値
これはチューリング還元を理解してれば
\begin{array}{lllllllllll} \displaystyle \Bigl(A≤_{T}B&∧&B≤_{T}A\Bigr) &&⇒&& A\equiv_{T} B \end{array}
直感的に分かると思います。
こういう関係にある時、
A と B はチューリング同値であると言います。
チューリング次数の厳密な定義
これは「チューリング同値関係 \equiv_{T} 」を使って
\begin{array}{lllllll} [X]&=&\displaystyle \{ S \mid X\equiv_{T}S \} \\ \\ \mathrm{deg}(X)&=&\displaystyle \{ S \mid X\equiv_{T}S \} \end{array}
\begin{array}{llllllll} \displaystyle X∈\mathrm{deg}(X) \end{array}
その「同値類」として定義されています。
初見だとまじで意味わかんないですね。
\begin{array}{llllll} \displaystyle X⊂N \end{array}
でもまあこれは基本『自然数』なので、
「加算無限 \aleph_0 」と「非加算無限 2^{\aleph_0} 」だけ押さえてれば
\begin{array}{lllllllll} \displaystyle \mathrm{Cardinal}(\mathrm{deg}(X))&<&\mathrm{Cardinal}(Y) \\ \\ \aleph_0&<&2^{\aleph_0} \end{array}
まあそんな難しい話じゃないと思います。
再帰定理 Recursion Theorem
|| 自分 → 自分ができる感じ
「計算可能関数」は自分で自分を記述できるよ。
これはそんな感じのことを主張する定理になります。
「クリーネの再帰定理」と言われることもありますね。
『不動点』とか『自己参照』とか
そういうのを扱うので詳細は別で。
ここではざっくりとした説明に留めます。
ゲーデル数
文字なんかに『紐づけされた自然数』のこと。
「符号化」する場合なんかで必要になります。
\begin{array}{llllllll} \displaystyle A &:=&1010 \\ \\ B&:=&1011 \end{array}
まあ要はこういうやつで、
この操作を「ゲーデル数化」と言います。
概念自体はそんな難しくないでしょう。
\begin{array}{llllllll} \displaystyle \mathrm{encode}(x_1,x_2,...,x_n) &=&2^{x_1} \times 3^{x_2} \times 5^{x_3}\times \cdots \times p_n^{x_n} \end{array}
ちなみにこういうのも
「ゲーデル数化」と言います。
S_{n}^{m} 定理
「パラメータ定理」とも呼ばれます。
『記号』と『変数』についての定理で、
\begin{array}{lllllllll} φ_{s(p,x)}&=&λy.φ_p(x,y) \\ \\ φ_{s_n^m(p,x_1,...x_m)}&=&λy_1,...,y_n.φ_p(x_1,...,x_n,y_1,...,y_n) \end{array}
\begin{array}{lllllll} \displaystyle s_1^1&=&s \end{array}
主張はこんな感じ。
「 φ_s 」は『再帰関数 s のゲーデル数』
「 s 」は『原子再帰関数』を表しています。
\begin{array}{rllllllll} \displaystyle f(x,y)&=&x+y \\ \\ λx&.&(λy.x+y) \\ \\ λxy&.&x+y \end{array}
\begin{array}{llllll} \displaystyle \mathrm{Func}(0,x,y)&=&f(x,y) \\ \\ \mathrm{Func}(n+1,x,y)&=&g(\mathrm{Func}(n,x,y),n,x,y) \end{array}
基本は「再帰関数」についての話ですね。
\begin{array}{lllllll} \displaystyle φ_{s_n^m(p,x_1,...x_m)}&=&λy_1,...,y_n.φ_p(x_1,...,x_n,y_1,...,y_n) \end{array}
これの「ゲーデル数」が ↑ のようになるって話で、
これによって『変数の具体的な符号化』とか
なんかそういうのがはっきりします。
不動点
関数を通した時に「自分 → 自分になる点」のこと
\begin{array}{lllllll} \displaystyle f(a)&=&a \end{array}
つまりはまあこういう点 a のことで、
まあだいたい 0 とか 1 とかがこれになりますね。
再帰理論では
『自己参照』を考える時にこの考え方が使われます。
\begin{array}{lllllllllllll} \displaystyle f&:&X&→&X \end{array}
\begin{array}{llllllll} \displaystyle a&∈&X \end{array}
\begin{array}{lllllll} \displaystyle f(a)&=&a \end{array}
だいたいの関数は不動点を持つ
こういうことを主張する不動点定理とかでもよく見ますね。
ロジャースの不動点定理
関数 F(x) が全域で計算可能なら不動点を持つ
これはこんな感じのことを主張しています。
まあそうだろな、ってなるくらいには
わりと直感的な定理です。
クリーネの第一再帰定理
「枚挙作用素」とか「帰納作用素」とか
そういうので『不動点』について語ってる定理です。
\begin{array}{llllllllll} \displaystyle \mathrm{Enumeration}(X)&=&\displaystyle \left\{ n \mid ∃A⊂X \,\, \Bigl( (A,n)∈\mathrm{Enumeration} \Bigr) \right\} \end{array}
\begin{array}{llllllllllll} \displaystyle \mathrm{Induction}(f)&=&f \end{array}
だいぶややこしいんで、
とりあえず「第二再帰定理と似たようなもの」だ
とでも思っておけばまあだいたいそれでOK。
クリーネの第二再帰定理
自己参照するプログラムは作れる
これはこういうことを言ってる感じの定理になります。
\begin{array}{llllll} \displaystyle f(0,x)&=&g(x) \\ \\ f(n+1,x)&=& h\Bigl( f(n,x),n,x \Bigr) \end{array}
これもだいぶややこしいですが、
クリーネの第一定理と同様
\begin{array}{lllllllllll} \displaystyle φ_p(e)&=&φ_e \end{array}
要は「不動点」についての定理なので
直感的にはわりと当然のことを言っています。
以上が「再帰定理」の感じです。
何回か言った通り、人間に扱えるかが主軸になります。
なので皆さん、わりとこの考え方使ってたりするんですよ。