そっくりコンピュータ(^^;
これは、某メーリングリスト(^^;に投稿
したものを若干修正したものです。
一応自分で思いついたのですが、残念ながらアイディア自体は
周知のものだそうです。それでは内容。
--
谷山浩子さんの「そっくりハウス」は次のような意味の歌詞です。
-------------------------------------------------------
そっくりハウスは家の中に
おんなじ形のおもちゃの家があって、その中に
おんなじ形のおもちゃの家があって、その中に
おんなじ形のおもちゃの家があって、その中に
...
-------------------------------------------------------
という感じの無限再帰歌です。この家の大きさの
合計を求めてみましょう。元の家の大きさを 1 として、
おもちゃの家が半分の大きさ(大きすぎるけど面倒なので)とします。
するとだれでも知っている様に、
1 + 1/2 + (1/2)^2 + (1/2)^3 + ... = 2
というわけで、大きさの合計は 2 となります。
それで、ここからが本題でありまして、これをプログラムで書いて
みましょうということなのです。一番自然(^^;なプログラムを C っぽく
書くと、
------------------------------------------------------
#include <sokkuriio.h>
real sum(int n); /* prototype */
int main() {
printf("%r\n",sum(0)); /* %r は real の表示 */
return(0);
}
/* 第 n 項以降の合計(^^;を求める */
real sum(int n) {
return(((1/2)^n) + sum(n+1)); /* (^^; */
}
------------------------------------------------------
だたし real は任意精度の実数を表現する型で、例のごとく int の
上限はないものとします。
あと '^' は XOR 演算子ではなく巾乗演算子です。
それで、もちろん上記のプログラムは一般のコンピュータでは
動作しません(^^;。
次のように計算が進む感じなのですが、なんといっても
終了条件がないですからね。「こんなことをしてはいけません」
と怒られるプログラムの代表ですね。
------------------------------------
sum(0) --->
1 + sum(1) --->
1 + 1/2 + sum(2) --->
1 + 1/2 + (1/2)^2 + sum(3) --->
...
------------------------------------
ところが大発明の「そっくりコンピュータ」を使用すると、
上記のプログラムがちゃんと停止して、「2」と出力するのです(^^)。
それで、「そっくりコンピュータ」の仕様ですが、
----------------------------------------------------
回路 S(0) があって、これは普通の CPU
S(0) の内部に、半分の大きさの回路(CPU) S(1) が
埋め込んであって S(0) の倍の速度で動作。
S(1) の内部に、半分の大きさの回路(CPU) S(2) が
埋め込んであって S(1) の倍の速度で動作。
S(2) の内部に、半分の大きさの回路(CPU) S(3) が
埋め込んであって S(2) の倍の速度で動作。
...
----------------------------------------------------
回路(CPU) S(n+1) の速度が、S(n) の速度の倍というのは都合が
良すぎる様ですが、半分の大きさなので、信号遅延も
半分になり技術的には何の問題もありません(^^;。
それで、どうしてこれでうまくいくかというと。
- まず全体の回路(CPU)の大きさは S(0) の大きさを 1 として、
そっくりハウスと同じ原理で 2 に収まる。これで筐体の問題は
解決(^^)。
- 上に書いた sum(n) の部分の計算を回路(CPU) S(n) に依頼する。
これで sum(n) の部分の計算時間は (1/2)^n となります。ただし
sum(0) の部分の計算時間を 1 とします。
これで合計の計算時間もそっくりハウス原理で 2 で収まります(^^)。
- スタックの心配がありますが、なんと回路(CPU) S(n) は内部に
ちゃんとスタックを持っているので大丈夫。
量は同じですが、そっくりハウス原理で、素子の大きさは S(0) と
比較して (1/2)^n ですみます。
無限を有限時間で計算する完璧なアイディアは出来ました。
私は不器用で作れそうもないので、
だれか実際に作ってくれませんか〜(^^)/。
