アルゴリズムは、たった３つの制御構造の組み合わせで記述することができることのハードウエアとからめた理解。

質問

すべてのアルゴリズムは、たった３つの制御構造の組み合わせで記述することができる。３つの制御構造とは、図1～3が示すような順次実行、分岐実行、繰り返し実行である
http://www.rsch.tuis.ac.jp/~kitakaze/2008/flow.html

とありますが、

以前、学生時代、教授がこれについて、ハードウェアとからめて説明していたのを
思い出します。

「ハードウエアを見ても、CPUがどうの、こうのだから、
順次実行、ハードウエアのここで分岐を実行して、
ハードウェアのここで反復実行をしている。だからソフトウエアとしてもこの３つの命令ですべてのアルゴリズムを記述できるわけだ」
というような感じの説明でした。

そのときは、なるほど深く理解しているひとは、アルゴリズムというソフトウエアと
回路、素子などによる構成物であるハードウエアと両方見て、合理的に説明する能力が
あるのだなと感心しました。
その具体的なひとことは残念ながら思い出せませんので質問します。

ハードウェアとアルゴリズムが３つの指令（分岐、繰り返し、順次）ですべて記述できること
の間の関係をうまく説明できる方はいますか？

よろしくお願いします。

回答No.1

kt1965 · ベストアンサー

第二次世界大戦中、エニグマというコンピューターを開発しているとき、アラン・チューリングという数学者が証明していますね。

もしも、無限大の時間があれば、全ての計算が出来ることを説明しています。この理論が基礎になって、現在のコンピュータの基本が生まれています。

基本は、無限大の長さのテープとヘッドからなります。ループを繰り返す制御構造に、分岐を加えれば、ループから抜け出せます。逐次計算を行えば、それで計算が出来ます。

それらの繰り返しが、ソフトウエアとハードウエアの基礎的構造になっているからですよ。

詳しいことは、Donal E.KunthのThe Art of Computer Programing の第一巻に出ていますよ。

回答No.2

Tasuke22

私はちょっと納得できません。

繰り返しは、分岐の応用ではないんでしょうか？
とてもアルゴリズムの基本とは思えません。

例えば、回路の基本は、and,or,notですが、eorは
それらの組合せで出来るので、基本から外れて応用
に感じるのと同じように思えます。

私の捉え方が違うのでしょうか？