再帰理論の初歩シリーズ「再帰定理」 - とりマセ

あ、超おひさしぶりです。 最近めっきり筆不精になってしまったので、リハビリ代わりに、再帰理論の初歩的な定理を紹介するシリーズでも始めようかなあ。 でも、シリーズとか言っておきながら、一回で終わったりするかも。せめて二回くらいはやれるように頑張ります。たぶん。 再帰理論と再帰定理 数学基礎論の一分野である再帰理論は、20世紀前半頃から研究され始めたそこそこ新しい分野です。といっても、数学基礎論自体が19世紀末から20世紀初頭に生まれた新しい分野なので、再帰理論は数学基礎論の分野としては結構古い部類だったりはします。 というわけで再帰理論の初歩シリーズ第一回は、再帰理論の再帰の名を冠する定理「再帰定理」の紹介。 この定理は、もしかしたら、プログラマさんとかの間では常識なのかも。 「再帰定理」とは、大雑把に言うと、 「プログラムに自己言及を含ませることができるよ〜」 「自己増殖をするプログラム

[maangie]

スティーヴン・コール・クリーネ。

[zyzy]

わかる様になりたいのでいずれちゃんと勉強しよう。

[usurausura]

オラクル相対化．証明不可能性

[smoking186]

relativizationの話が後半にある