過去・現在・未来

ファインマンの「量子コンピュータによる自然のシミュレーション」という刺激的な問題提起を受け、それを「計算可能性理論」の中心的な原理である「チャーチ＝チューリングのテーゼ」との関連で整理しなおして「計算可能性」を再定式化したのは、ドイッチェである。 1985年の論文 "Quantum theory, the Church-Turing principle and the universal quantum computer" https://goo.gl/PVHGKa  で、ドイッチェは、「チューリング・マシンのクラスの量子論的一般化である計算機械のクラス」＝「万能量子コンピュータ」を構成して見せる。 彼は、「チャーチ＝チューリングのテーゼ」を次のように捉える。 『「計算可能と自然に見なされる関数」は、全て、万能テューリング・マシンで計算可能である。.』 ただ、彼は、この「チャーチ＝チューリングのテーゼ」の基礎には、暗黙の物理学的主張がある」という。これが、この論文の眼目である。 彼は、彼が構成して見せた「万能量子チューリング・マシン」＝「万能計算機械」を用いて、「チャーチ＝チューリングのテーゼ」を書き換える。 「この物理学的主張は、次のような物理学的原理として、明確に表現することが出来る。」 『有限な方法で実現可能な物理システムは、有限な手段によって操作される万能計算機械のモデルで完全にシミュレート可能である。』 これを、「チャーチ＝チューリング＝ドイッチェのテーゼ」という。 ドイッチェは、論文で、これらの原理が、次の熱力学の第三法則に似ていること注意を向けているのは、興味ふかい。 『どのような有限のプロセスも、有限な手段実現可能な物理システムのエントロピーあるいは温度をゼロにはできない。』 形式的・数学的で抽象的な「計算可能性」の原理だった「チャーチ＝チューリングのテーゼ」は、ここに「チャーチ＝チューリング＝ドイッチェのテーゼ」として、実在的な過程としての「計算」の原理として「物理化」されることになる。 「計算可能性」の原理の「物理化」は、関連する諸科学に、一つのインパクトをもたらすことになる。なぜなら、それは、それまで別々の学問の対象だった「計算過程」「物理過程」「情報過程」（それぞれ、数学・物

「計算可能性」の理論として出発した「複雑性理論」が、質的な深化を果たすのは、1980年代になってからである。 大きな転回点になったのは、1982年のファインマンの論文 "Simulating Physics with Computers" https://goo.gl/ueVbdp  である。 この論文は、複雑性理論の進化の重要な画期を与えるとともに、現在の量子コンピュータのアイデアの出発点ともなる重要な論文である。（同時に、現在の量子コンピュータ技術の到達点は、ある意味、この論文への「回帰」として特徴付けられるのは、興味ふかいことである。） ファインマンは、次のように述べる。 「コンピューターが、正確に自然と同じように振る舞う、正確なシミュレーションが存在する可能性について話そうと思う。 」 「それが証明されて、そのコンピュータのタイプが先に説明したようなものであるなら、必然的に、有限の大きさの時空の中で起きる全てのものは、有限な数の論理的な操作で正確に分析可能でなければならないことになるだろう。」 「量子論的なシステムは、古典的な万能計算機で、確率論的にシミュレートされるだろうか？」 「 別の言い方をすれば、コンピューターは、量子論的なシステムが行うのと、同じ確率を与えるだろうか？　コンピューターを今まで述べてきたような古典的なものだとすれば（前節で述べたような量子論的なものではないとすれば）、また法則はすべて変更されないままで、ごまかしもないとすれば、答えは明らかにノーである。」 「それは、新しいタイプのコンピューター、量子コンピューターで可能になるだろう。」 「 私が理解する限りでは、それは量子論的なシステムによって、量子コンピューターの要素によって、シミュレート出来るようになることは、いまや、明らかになった。それはチューリング・マシンではない。別のタイプのマシンである。」

1950年代に入ると、時代の先鋭な知性たちは、今日の複雑性理論の原型とも言える認識に到達し始める。 スコット・アーロンソンは、複雑性理論の到達点を概観した論文 "N = NP?"   https://goo.gl/TZUkgh  の冒頭に、ジョン・ナッシュの 1955年のNSA（スノーデンがいた、あのSNAだ！）宛の手紙をあげている。かつては「機密文書」とされていて、いつかの時点で情報公開されたものらしい。 誰にも破れない暗号を作るためには、指数関数的な計算が必要な暗号を作ればいいことを述べている。また、そうすれば、それまでの職人技的な暗号破り（多分、チューリングやファインマンがしていたこと）は「過去」のものになると、明確に自覚している！ ----------------- 　現時点での、私の一般的な予想は次のようなものです。： ほとんどすべての十分に複雑なタイプの暗号化にとって、特に、鍵の異なる部分によって与えられた命令が、相互に複雑に相互作用して、それが暗号化の最終的な決定において影響を与えている場合、鍵の計算の平均的な長さは、鍵の長さ、すなわち、鍵の持つ情報の内容に関して、指数関数的に増加します。 　もし、この予想が正しいと仮定すれば、この一般的な予想の重要性を理解するのは容易です。それは、実際的には誰も破れない暗号を設計することを、極めて簡単に実行できることを意味します。暗号が洗練されたものになるにつれて、熟練したチームなどによる暗号破りのゲームは、「過去」のものになっていくはずです。 　この予想の性質は、たとえ特別な種類の暗号をとっても、私にはそれを証明できないようなものです。また、私は、それが証明されることも期待していません。」 ----------------- https://www.nsa.gov/news-features/declassified-documents/nash-letters/assets/files/nash_letters1.pdf 現文は、こちら。 僕は、ナッシュのNSAへの手紙は知らなかったのだが、有名なのは、1956年にゲーデルが、フォン・ノイマンに宛てた、次の手紙である。ゲーデルが、ほとんど完全に、問題の所在を把握していることがわかる。 -----

「サイエンス」誌の今日のニュースから。 「脳は、睡眠中にアルツハイマー病の病因物質をきれいに取り除いているのかもしれない」 https://goo.gl/mNxdY8 アルツハイマー病は、脳内に、アミロイド・ベータという物質が蓄積して起きることは知られているが、この記事は、アルツハイマー病の発症過程と睡眠との関係を論じたもの。 睡眠不足が続くと、脳内にアミロイド・ベータの蓄積が進むという実験の紹介がメイン。一方で、睡眠が、脳活動に伴う廃棄物の除去に重要な役割を果たしているという、「睡眠＝ガーベージ・コレクション（ゴミ集め）説」を紹介している。 寝ている間に、脳の中では、アルツハイマー病の原因物質の掃除が行われているかもしれないということ。このイラスト面白い。 アルツハイマー病の予防に、きちんとした睡眠をとることが重要というのは、常識的にも納得できるとおもう。 IT業界にも多い「睡眠不足自慢」の人にも、ぜひ読んでほしい。20代〜30代の若い人では、睡眠不足が続いても、急速なアミロイド・ベータの蓄積は見られなかったという実験もあるという。これも、経験的には納得できる。でも、そうした生活を長く続ければ、どうなるかということ。アルツハイマーの発症までには、長い年月がかかる。たいていは、65歳以上からなのだから。 個人的には、睡眠サイクルがちょっと変で、ある人からは「寝ない人」だと思われているのだが、でも大丈夫（多分）。ある人が言うように、「寝てばかりいる人」だから。 （LISPやJavaをやっていたものとしては、「睡眠＝ガーベージ・コレクション説」は、ちょっとささった。さあ、ボケ予防のため、はりきってガーベージ・コレクトするぞ。） コメント 中野 正和   熱いものを触ると手を引っ込める、所謂「反射」の根本が、五感それぞれに存在していて、味覚なら嘔吐を促す苦味ですが、視覚や聴覚でもキャパ(限界量)があって、入力過多を起こすと、何らかの反射をすると思います。4,5日寝ないと幻覚や幻聴が出ると言う話を聞きますね。心療内科だと「3日寝ないと死ぬ」と言う話があるそうです。 1 管理する いいね！  ·  返信  ·  5日前