万能な記述形態って何種類あるのでしょうか？

Question

プログラマをやっています
プログラミング言語を見ていくと

・アセンブラ→C言語→Javaの流れ
チューリングマシンから、よく使うものを文法として括り出してきた
・Lisp
ラムダ算法をプログラミング言語に落とし込んだ
・Prlog
述語論理をプログラミング言語に落としこんさ

という風に、それぞれ元になっているモデルが違いますが
それぞれが万能な記述形態で、どんな計算でも出来る記述携帯になっています

それで疑問に思ったのですが
他にも万能な記述形態として知られている算法というのは他に何種類あるのでしょうか？

大学の初等数学までしか知らない人間レベルで分かる解説サイトなどもあれば教えて下さい

stomachman · Accepted Answer

「プログラムの意味論(semantics)」という（ちょっと難しい）分野の話です．というのは，万能性を証明するとは「あるプログラムがチューリングマシンのシミュレータになっていること」あるいは「任意の帰納的関数を表現できるプログラムが存在すること」を証明することに他ならない．だから，プログラムの意味を記述する必要があるわけです．

プログラミング言語との関連で言えば，計算機のハードウエアなんてものは忘れて，計算を，ある抽象的な数学的システムの上でのプロセスと考える．（なのでハードウエアのアーキテクチャをムキダシで扱うアセンブラやCのような低級言語はちょっと脇に置いときます．）その「抽象的な数学的システム」の捉え方がいろいろある，という話かと思います．
　ご質問で例に挙げられたのは，計算（プログラムの実行）を，変換の手順（手続き）の遂行と見るか，写像の不動点へ近づく過程と見るか，論理式が恒偽式であることの証明を自動生成することと見るか，ということでしょう．
●手続き：メモリやレジスタの中身を書き換えていくという操作，および，ある計算システムの出力を別の計算システムに入力として与える，という結合．
●証明：一階述語論理は証明が可能．導出原理を使えば機械的に行えますが，場合分けが猛烈に沢山発生して遅い．そこでprologでは導出原理を線形導出の一種に限定して，計算を「反例を探すプロセス」とみなす．(万能性の観点からは，カット演算は本質的ではありません．)
●不動点： 関数の引数に値を代入(λ計算)する，という操作を繰り返すことで，その関数の不動点に到達する．ループを使わずrecursionで計算を行うという場合だけでなく，ループを一つの関数と捉える方法(たとえばHoare論理におけるinvariant assertion)もあります．

いずれも「状態」を１ステップずつ変化させていくプロセスであることには違いがありません．そしていずれも，個別の１ステップにばかり注目するのではなくて，一連のステップ全体がどういう性質を持つかをまとめて扱うための仕掛けを持っている．
　ただ，そのまとめ方にバリエーションがあるということですね．効率（計算量）の話は無視して万能性についてだけ見ますと：
●手続き: 「ある計算システム(subprogram)の入出力の関係」さえ分かれば，その内部はどうでもいい．
●証明: ある論理式が真か偽かということが分かれば，以後，その証明のプロセスの詳細はどうでもいい．
●不動点：ある関数の，不動点という行き着く先が分かっていれば，そこにどういう経路で到達するはどうでもいい．

こうした仕組みを使うことで，細部をブラックボックス化し，プログラム全体の意味をひとまとめにした論理式を機械的に構築できるようになる．
　なお，個別のプログラムについて具体的にこの構築をやるのは「プログラムの正当性の検証(verification)」という分野の話です．これを言語に組み込んだのはEuclidなど．Javaにもその一部(assertion文)が入っていますね．

ようやくご質問の「他に何種類」という話ですが，いや，分かりません．てか，何かテキトーな数学の概念、あるいはゲームなどにこじつけてプログラミング言語（と、その意味論）を作れば，バリエーションはいろいろ出来る気がします．で，なんでそんな気がするのかは，以上の話でナントナク感じ取れていただけたのではないかと．
　なお，現実のプログラミングでは万能性なんかより性能が問題になるわけで，「計算量の理論」は（かなり難しいけれど）勉強してみる値打ちがあります．具体的な性能の話では「計算幾何学（計算機科学じゃないです）」が大いに参考になるでしょう．あるいは逆に，計算というものを，万能性に拘らずにもっと緩やかに捉えることができるアプローチとして，たとえば（めっちゃ難しいけれど）「情報幾何学」なんてのもあります．

ddtddtddt · Answer

自分もプログラマーやってます。答えではありません・・・感想のような、コメントのような・・・。

じっさいにApplication開発をやっていると、言語モデルより開発モデルの方へ目が行ってしまって、言語モデルなんか余り意識していません。まぁ～、ふだん使ってる言語はどれも、通常の要求に対しては普遍解法があるものだと信じて、プログラムを書いてる訳です（そうでないと書く気にならない(^^)）。

それで思ったのですが、この質問の動機はどういったものなのでしょう？。緊急度「緑」なので、たんなる興味かも知れませんが、同じ職業をやってる方が、自分がふだん意識しないところに興味を持たれたという事で、逆にその理由にとても惹かれました。よければ教えて下さい。

で、これだけではルール違反なので、関連ありそうな書籍を上げます。

(1)知の限界，Ｇ・Ｊ・チャイティン，(株)エスアイピーアクセス，2001年．
　　　　チューリングマシン→ラムダ計算→不完全性定理、という流れの本です。まぁ、この手の本としては普通の値段で薄いです。中に上記の流れに関する、Lispコードが随所に現れ、Lispに慣れてない自分は「頭痛かった」ですが、Lispに慣れてるなら、すらすら読める気がします。

(2)コンピュータプログラミングの概念・技法・モデル，ピーター・ヴァン・ロイ他，(株)エスアイピーアクセス，2007年．
　　　　お高いです。分厚いです。大学の図書館なんかで探すべき本です。実用とかコード書き訓練ではなく、学問としてのプログラミング学を記述した、本邦初公開の成書と思われます。記述の基礎は、チューリングマシンにあるようですが、話はグラフィカル・インターフェイスの範疇にまで及びます。高くて分厚いので、自分は当然読んでません。

以下、余談です。

自分の常備品は、VB（Rapidなので），VC（VBのパワー補完），VF（Visual Fortran，計算腕力）なのですが、公理的集合論を読んだ時に、次のような事を思いました。集合論の前段には、第1階述語論理（命題理論含む）を一通りやります。

・命題理論の組み込み型→関係式と対象式．
　　・命題理論の補助仮定の方法→サブルーティン・コール．
　　・命題理論の補助定数の方法→サブルーティンのLocal変数（スタック上）．
　　・命題理論における定義→整数型，文字列型とかの組込型の定義、またはClass定義の型定義と同じ．
　　・述語理論の量化子「∃」→領域（メモリ）確保＝変数宣言→集合の存在．
　　・述語理論の量化子「∀」→プログラミング言語にはないので、手続き処理する→じつは「∃」による「∀」の定義と同じ．
　　・超限帰納法→メモリ制限なしの再帰手続き．

・・・などなどです。自分はいちおう公理的集合論を理解してると（勝手に）思ってますが、そのとき役に立った（と思える）のが、上記のようなプログラミング言語の構造との対応付けでした。

・・・という訳で、あくまで、感想のような・・・コメントのような・・・(^^；)。

Tacosan · Answer

とりあえず C や Java はチューリングマシンからもっていくより RAM からもっていったほうが簡単だと思うし, Prolog はもともと 1階述語論理でしかもホーン節しか使えないので「カットがすべて」のような気がする.

あと, D∞ とか組み合わせ論理は思いつく. ほかにもありそうだけど....

万能な記述形態って何種類あるのでしょうか？

自分もプログラマーやってます。

この回答への補足

とりあえず C や Java はチューリングマシンからもっていくより RAM からもっていったほうが簡単だと思うし, Prolog はもともと 1階述語論理でしかもホーン節しか使えないので「カットがすべて」のような気がする.

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

　自分もプログラマーやってます。