  |
はてなキーワード: チューリング完全とは
「漫画家イエナガの複雑社会を超定義」の「量子コンピューター」の回がこの後1:20からNHK総合で再放送するようなので、本放送を見たときの自分の感想を改めてここにまとめる。
一般のメディアにおける「量子コンピューター」の取り上げ方はいつも、専門知識を持っている人間から見たらとんでもない誇張と飛躍で充ちている。もはやSTAP細胞詐欺か何かに近い危険性を感じるので、こういう話に接する時の注意点、「ここを省略していることに気づくべき」要点を解説する。
メディアにおける「量子コンピューター」の説明は、大体いつもストーリーが似通っている。
件の軽い調子の番組だけでなく、ニュートンだろうと日経サイエンスだろうと、まあおおよそ複素関数論の「ふ」の字も紙面に出したら読者がついてこれなくなる程度のメディアではほとんど同じ構成である。
これはこの20年ほど変わらない一種のパターンになっているが、実はこのそれなりに繋がっているように見える一行一行の行間すべてに論理的な問題を孕んでいる。
この行間に実は存在する論理の省略、あるいは嘘と言っても良い誤摩化しをひとつひとつ指摘していこうと思う。
量子ビットには重ね合わせの状態が保持できる。これに対して計算処理をすれば、重ね合わせたすべての状態に並列に計算を実行できる。ように見える。
しかし、これも一般的に聞いたことがあるはずなので思い出して欲しいが、「量子力学の重ね合わせの状態は、『観測』により収束する」。
つまりどういうことか？ 量子ビットに対する処理が並列に実行出来たとしても、量子コンピュータの出力はそれをすべて利用できるわけではない。
量子コンピュータの出力とは、量子ビットに対する並列処理の結果の、確率的な観測に過ぎない。
なので、手法的な話をすれば、量子アルゴリズムとはこの「確率（確率振幅という量子状態のパラメータ）」を操作して、望む入力に対する結果が観測されやすくする、というちょっとひとひねりした考え方のものになる。
単に並列処理ができるから凄いんだという説明は、増田自身一般向けの説明に何度も繰り返したことがあるが、まあ基本的には素人相手の誤摩化しである。
ここさえ踏まえれば、知識がなくともある程度論理的にものを考えられる人には、量子コンピュータに対する色々な期待も「そう簡単な話ではない」となんとなく感じられると思う。
量子コンピュータのキラーアプリとされている暗号解読は「ショアのアルゴリズム」という非常に巧妙な計算を通して得られる。
上で説明したように、量子コンピュータは単に「並列計算だから」なんでも高速な処理ができる訳ではない。暗号解読については、この「ショアのアルゴリズム」という自明でない計算手法（高速フーリエ変換の応用）が見つかってしまったからこそ問題になっているのであって、このアルゴリズムの実行が出来なければ暗号解読ができるとは言えない。
さてここからは量子力学というより計算機科学の話になるが、あるチューリングマシン上のアルゴリズムが別の計算モデルで実行可能かどうかは、その計算モデルがチューリング完全であるかどうかによるというのはプログラマには常識である。
これは量子コンピュータにおいても変わらない。量子コンピュータの一般に知られる多くのアルゴリズムはドイチュの量子チューリングマシンを前提に作られており、チューリング完全でないアーキテクチャでは実行できない。できるはずがない。ショアのアルゴリズムも当然そうだ。
しかしながら、この20年弱、D-Wave社が最初の「自称・量子コンピュータ」を開発したと発表して以来、さまざまな企業が「開発に成功した」と発表した「量子コンピューター」の中で、このチューリング完全なものは何一つ存在しない。
これらでは、今後どれだけ「性能」が伸びようとも、暗号解読の役には立たないのである。
以上の議論から総合すればわかると思うが、量子コンピュータで世界が一変するなんてヴィジョンははっきり言ってSF以下のファンタジーというレベルでしかない。
第一に、量子コンピュータの利用できるドメインは非常に限られたものであるし、第二に、その中の最も宣伝されているものである暗号解読の可能な量子チューリングマシンの開発の目処などまったく立っていない。どころか、業界のほとんど誰も挑戦することすら本気では考えていない。
現状の「自称・量子コンピュータ」（量子情報システム、とでも言おうか）にも利用の可能性はある。何より量子状態そのものが作れるので、物理学や化学領域の量子システムをシミュレーションするのに適しているのは言うまでもないだろう。しかし、まあ、現状あり得る比較的現実味のある用途というのは、それくらいではないか。
このように、メディアが量子コンピュータについて語るとき、そこには非常に多くの誤摩化しや飛躍が含まれる。これは結構業界の根幹に関わる問題なのではと思うが、時間が来たので総括は後述にでもすることにする。
何か質問があればどうぞ。
コンピュータ・サイエンスで取り組まれている問題の一覧を紹介しよう。
いやぁ、長かったですね。Python が業界デファクトスタンダードになり、シェル言語やシステム記述言語となる可能性が潰えて久しくなるまでが。具体的にいうと Ansible のようなクラウドの構築はTerraformになったし、Linuxのブートには systemd が後継となったいま、Python は Ruby と同じく「Perl のような何か」に落ちてしまった。唯一無二の人工知能の為の言語としても、高度化した人工知能の開発で新規参入者にとってはハードルが高く、API を操作するぐらいだったら JavaScript で JSON をコネコネする API を操作するほうが賢い時代となってしまったのだ。よって Python を新規で採用する絶対的なメリットは消えてしまった。これで「Pythonを使えます」という奴に見下される必要はなくなったのだ。これで、ここ数年間も続いた「Pythonを使えるのを凄いと勘違いしている間抜け、または人工知能の開発で Python は必須なのとかぬかす馬鹿、それに Python を使えば他言語を学ぶ必要はないというキチガイ」を排除できるようになった。だって、Python は数多の言語のようにチューリング完全を満たした言語の一つになったのたから。これを普遍的と言わずになんていうのだろうか。
ブロックチェーン界隈は邪悪な人間が多いためか、ブロックチェーンに否定的なITエンジニアが多いのだけど、とてももったいないことだと思う
邪悪な人間は嫌いになってもいいけど、ブロックチェーンのことは嫌いにならないでほしい
イーサリアムを作ったヴィタリックさんは、イーサリアムのことを「ワールドコンピュータ」と呼んでいます
コンピュータというのは、記憶領域と入出力装置を兼ね備えた演算装置のことです
記憶領域はブロックチェーンのブロックの部分が担っており、演算装置はマイニングマシンが担っています
入出力の出力の部分は、演算装置が計算して記憶領域に格納した結果をこちらから読み取り行くことで実現でき、
入力の部分は「オラクル」と言われることもあるけれど、データをブロックチェーンに流しこむことで実現できます
ブロックチェーン同士をつなぐブリッジも一種の入出力と言えるでしょう
つまり、これら記憶領域や演算装置を持つブロックチェーンは、コンピュータなのです
コンピュータにやらせたいことはスマートコントラクトというプログラムコードに書きます
チューリング完全だそうです
そのコンピュータを操る基本ソフトであるOSは、ブロックチェーンに組み込まれているので、ブロックチェーンを作るということはOSを作るということなのです
普通のコンピュータの場合、フォルダの中身を見るのにエクスプローラーを使いますが、ブロックチェーンにもエクスプローラーはあります
ブロックの中身を見たり、スマートコントラクトのコード(ソースコードが公開されていない場合はバイトコード)を見たりすることができます
このエクスプローラーはブロックチェーン自体が備える機能ではないけれど、ブロックチェーンがコンピュータっぽいことが分かるのではないでしょうか
ちなみに、スマートコントラクトはコンピュータにインストールするアプリに相当するでしょう
web1.0が登場したころ、そのあまりの遅さゆえwwwのことを「world wide wait」と揶揄する人もいたそうです
webはその後劇的に速くなったので、ブロックチェーンも速くなるかもしれません
話が長くなりましたが、言いたいことは、ブロックチェーンは詐欺ツールではなく、ただの技術です、ということです
現状、詐欺を支える技術となってしまっている部分もありますが、技術自体はニュートラルです
ブロックチェーンは、プライベート、コンソーシアム、パブリックに分けて考えた方がいいかも。
プライベートチェーンは管理者がいるから簡単に改竄できちゃうので、ブロックチェーンの良さである耐改竄性はあまり発揮されない。なのでわざわざブロックチェーンを導入するよりかは、普通のデータベースを使ったほうがいいと思われる。ただ、上の増田が書いているように、中央銀行デジタル通貨の基盤として使うのには相性いい気がする。
コンソーシアムチェーンは耐改竄性が求められるのでブロックチェーンと相性がいいと思う。貿易事務の領域で導入されて「業務が効率化されました」って記事を最近見たけど、このケースではデータベースとして使うというよりはEDI的な使い方をしているのかも？ 他の活用例はあんまり見ない。業界が協調して動かないと意味ないから導入が難しいのかも？
パブリックチェーンは暗号通貨の領域。この領域は投機的な話だらけで確かに面白くない。ただ、パブリックチェーンをスマートコントラクトのプラットフォームだと考えると話は変わってくる。スマートコントラクトにはチューリング完全なプログラムが書けるので、パブリックチェーンはデータベースというよりも巨大な一つのコンピュータと考えることができる。プライベートチェーンでもコントラクトは書けるけど、パブクリックチェーンの場合は誰でも参加できるというプラットフォーム性を備えていることが利点。管理者すなわちスーパーユーザがいないという点も大きなメリット。
今の所はポンジースキームのプロダクト、あるいはステーブルコインを使ったペイメントぐらいの活用例しか見ないんだけど、パブリックチェーンが一番ポテンシャル高いと思う。
Scala や Elm と Lisp やら Haskell と OCaml に SML と関数型のプログラミング言語を勉強したけど、これらが命令型言語に劣る理由を解説しよう。
これは、SQL も同じ問題を持っているが、関数型言語は「こういうふうに動いてね」という解釈をインタープリターやコンパイラが「推測する」必要があるのだ。つまり、書いているときにパフォーマンスをプログラマーが想像できない。
それが、現実的に厳しいのだよ。マジでコンパイラ関連は金にならない領域になってきたので、関数型言語のための独自コンパイラを作る持続可能な組織が無い。確かに、LLVM を使えば x64 や arm といった最新のアーキテクチャに対応できるかもしれないけど、フロントエンドのレベルすら応対が辛い。よって、関数型言語は C言語にてチューリング完全な同等なコードだと「いくら最速に書いても」遅いのである。
例えば if と書いたら、関数型言語は else が必須ですが、命令型言語は else 無しでも動いちゃうのですね。文系の連中が数学的な背景を加味して要件定義できると思うか？違うだろ。毎回、上に else のことについて聞いたら、プログラマーの生産性は下がるだろ。関数型言語は、上が文系だとますますだが、分岐もきっちりとおさえる必要があるから、生産性は命令型言語に劣るよ。
もと増田だけど、気分まぐれに書いた駄文なので気にしないといてくれ。
それはさておき、Python が好きってことはプログラミングが好きってことで良いね？だとすると、最終的には C 言語やることになるけど、今は Python をやろう。なんと言っても、Python は C 言語できているけど、C言語は謎いので無視してオッケー！
そんでもって、Python の「公式ドキュメント」をきちんと読みこなせるようになろう。最初はから全部は必要ないけど、最終的には読みこなせるようになろう。そんでもって、プログラミングをしたいってことは「何かを作りたい」のだろ？たとえば、増田を作りたかったら Python だと Django や Flask を、人工知能を作りたかったら PyTorch を使うことになるだろうけど、その手のフレームワークの「公式ドキュメント」を読みこなせるようになろう。プログラミングスクール（やめとけよ）や本は「公式ドキュメント」を読めるようにする手段だと思ってくれ。間違っても「本に書いてあったのに、動かない！」なんて、喚かないでね。洋書も和書も「公式ドキュメント」以外のテキストは間違っていることがあるので。
次に「エラーは友達」ということ。エラーはあなたを否定したのでなく、コードを否定したのであって、エラーが出ても気にしないでください。そんでもって、エラー文を丁寧に解決していけば、すごくスキルが身につきます。
最後に、Python 言語だけじゃ解決できないプログラミングの問題は多々あります。データベースを操作するには SQL が、ウェブサイトを動かすには JavaScript が、ウェブサイトを作るには HTML/CSS が、サーバーを設置するにはシェル言語が、Python を高速化するには C言語が、必要になる場合がありますが Python を使いこなせると、おそらく習得は容易でしょう。なぜかというと「Python だとチョメチョメだったっよなー、これでいけないか？」という勘が形成されるので。
チューリング完全な言語はどれも表現力は同じだから、「この言語だから成功する」というのは無いよ。Python は interface が無くて、class が弱くて、動的型付けを用いているけど、これらがないと「制約」を課すことができないというフリーダム過ぎるから、嫌らわれることはあるけどね。制約が強い言語は、ハンターハンターふうに言うと「制約が念能力を強くする」みたいな要素はあるよ。
どうしても教育を受けたいという希望があるのなら、ハーバードの CS50 という講義が無料で見れるから、推薦したいね。あれみると、我が国は計算機科学は負けていると思った。
...ちょっと調べてみて分かった。思い込みでいろいろと書いていたが、Scratchはチューリング完全だし、ちゃんと再帰なんかも書けるのね。
ただ、配列が基本データ型にないのはアルゴリズム学習の観点からはかなりマイナスだと思う。
リストと配列はその振る舞いや扱いが大いに違うので、実装の詳細だから触れないでいいというわけにもいかないのではと思う。
そして、Chrome拡張を使えば競技プログラミングもできなくはないけれど、それだったら最初からC++書いたほうが早くね？とも思ってしまう。
たぶんエントリーはそこでもいいし、それでそれなりにアルゴリズムを勉強できるけれど、それ以外の言語を知らないというのはかなりのマイナスポイントなのではないのだろうか。
