「計算的な深さ」について - 186 @ hatenablog
▼ 「計算的な深さと脳」 で書いた計算的深さの概念はシンプルかつ重要だと思う。 もしそうならこの程度の概念がすでに専門の学者によって発明されていないはずはない。そう思ったのだけど、相変わらず私のアンテナにはかかってこない。もしかしたらまだ存在しないのだろうか。 (中略) ここで、試論として、「2入力NANDゲートだけで最速な回路構成をした時の計算時間」と定義する。こうすれば大きさNのメモリによる解決はlog N時間かかる事になる。同じ問題を、テーブルで解いてもハードワイアードロジックで解いても同じ程度の時間になるだろう。 ご想像の通り, 既にあります. (並列計算量とか回路計算量の文脈で調べると良いんじゃないかと.) Complexity Zoo - Qwikiから引っ張ってくると, こんな感じ. ACi 多項式サイズ/unbounded fan-in/AND, OR, NOT/深さO(l
計算的な深さと脳
ニューロンが入力を受けてからスパイクを出すまでは早くとも数ミリ秒かかる。人間が反応するまでの時間は零点何秒かだから、入力と出力の間には最大に見積もっても数十段のニューロンが介在するだけである。（実際はもっと段数が低いだろう。） 一方コンピュータの方は現在のネズミ以下の判別能力しかないような画像認識をするにあたってさえ数千万サイクルの計算を行わなくてはならない。 だから、脳が物凄い並列計算をやっているに違い無い。ここまでは普通の話ね。 で、問題は「じゃ、物凄い並列な機械をつくったら脳の能力を再現できるのかよ」ということ。もちろん誰も答えをしらない。どんなアルゴリズムを使えば良いか分からないし。 人によっては絶望して「新しい物理法則を」とか「量子論的並列性」とか、「魂」とかに行っちゃう。 で、僕も答えは持って無いけど、この問題を考えるにあたって以下の「計算的大きさ」と「計算的深さ」の概念を
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
