数学基礎論スレのスレタイを決めるスレ
■ このスレッドは過去ログ倉庫に格納されています
0522132人目の素数さん
2011/11/16(水) 04:39:29.05> ★★★『計算機言語Aでは表現出来なくて、でも別の計算機言語Bでは
> 表現が(実装が)可能であるという様な実例はないのか?』★★★
> という疑問であって、日本語・フランス語は単なる比喩です。
計算機言語というのがプログラミング言語のことであり、実装すべき処理がsequentialであれば、
少なくとも広く知られているプログラミング言語同士では原理的な表現能力は同等です。
つまり原理的に万能チューリングマシンで書ける処理は一般的に使われているどのプログラミング言語でも書けます。
逆に言えば、実用的なプログラミング言語はチューリングマシンで計算できる範囲全てをカバーするように設計されています。
(少なくとも十分に巨大なメモリを用意したコンピュータの上で実行できるならば)
あとは実装すべき処理に応じて自然に書ける(書きやすい)かどうかという工学的な違いだけです。
(実用面からはこの違いは小さくありませんが理論上は議論すべき余地はありません。なぜならば「自然に」とか「書きやすい」という概念を
十分な客観性を持つ形で定義できないからです)
ただし、必ず停止する事が保証されている「プログラミング言語」(というよりも各種の型付きλ計算の様な形式的体系)となると話は違ってきます。
なぜならば停止性が保証されている「言語」は決して万能では有り得ないからです。(言語が再帰的=ある句がその言語としてwell-formedか否かを
常に決定可能である限り)
逆に言えば、停止性が保証されている再帰的な言語は、どんな強力なものでも、必ずその言語では直接的にも意味的に等価な処理に書きなおそうとしても、
絶対に実装できないsequentialな処理が常に存在します。
例えば、simply typed lambda-calculus で書けるものはGirardのF(正確にはF_2)で書けるものの真部分集合であり、F_2はF_3に対して同様であり、・・・
それらいずれもはF_ωで実装できる範囲の真部分集合です。しかし最後のF_ωにしても、どんな入力に対しても必ず停止する処理であるにもかかわらず
実装できない処理が残るのです。simply typed lambda-calculus とF_2の表現能力の限界については、80年代前半にFortune, O'Donnell & Leivantが
JACMに発表した論文が読みやすいでしょう。
■ このスレッドは過去ログ倉庫に格納されています