FC2ブログ

再帰定理?

>計算論の「再帰定理」では、再帰関数を使用したプログラムを
>ループと条件分岐を使ってgotoなしで書き換えられる、ということを証明している。

一部表現を変えてありますが、そんな記述を見つけて。
それは「構造化定理」なんじゃないかと。

証明は再帰的な定義を許容するプログラミング言語と
ループと条件分岐があって再帰的な定義とgoto文がないプログラミング言語が
それぞれチューリング完全であることを示せばよいと。
まぁいちいちやるきは起きないけど
それほど難しくはないだろう。


ちなみに「再帰定理」は
引数を1つ以上とる任意のプログラムAについて
あるプログラムBがあって、プログラムAの引数としてプログラムBを代入した結果と
プログラムBを実行した結果が等しくなる。
正確な表現ではないけど、翻訳するとこんなところ。

これを面白いと思える人が多いと、いいなぁ。
関連記事

コメントの投稿

非公開コメント

a8
最近の記事
月別アーカイブ
ブログ内検索
グリムス
フリーエリア
リンク
RSSフィード