「Smn定理」の版間の差分
削除された内容 追加された内容
m ボット: 言語間リンク 5 件をウィキデータ上の d:Q1766814 に転記 |
Sillycrown (会話 | 投稿記録) 編集の要約なし |
||
1行目:
{{記事名の制約|title=s<sub>mn</sub>定理}}
'''s<sub>mn</sub>定理'''もしくは'''パラメータ定理'''とは、[[再帰理論]]における[[定理]]であり、[[プログラミング言語]]（より一般化すれば、[[計算可能関数]]の[[ゲーデル数]]）の基盤となっている<ref>{{cite book | author = Soare, R.| title = Recursively enumerable sets and degrees | series = Perspectives in Mathematical Logic | publisher = Springer-Verlag | date = 1987年 | id = ISBN 3-540-15299-7 }}</ref><ref>{{cite book | author = Rogers, H. | title = The Theory of Recursive Functions and Effective Computability | publisher = First MIT press paperback edition | date = 1987年 | origyear=1967年 |id = ISBN 0-262-68052-1 }}</ref>。これを最初に証明したのは[[スティーブン・コール・クリーネ]]である<ref>{{cite journal | author = Kleene, S. C. | title = General recursive functions of natural numbers | journal = Mathematische Annalen | volume = 53 | pages = 727–742 | date = 1943年 }}</ref>。'''s-m-n定理'''と表記されることもある。
この定理を実用的に解説すると、あるプログラミング言語と正の整数 ''m'' と ''n'' があるとき、''m''+''n'' 個の[[自由変数と束縛変数|自由変数]]を持つプログラムの[[ソースコード]]を操作する特定の[[アルゴリズム]]があることを示している。そのアルゴリズムは、与えられた ''m'' 個の値を最初の ''m'' 個の自由変数に束縛し、残りの変数を自由変数のままにしておく。
| |||