  |
はてなキーワード: チューリングマシンとは
「漫画家イエナガの複雑社会を超定義」の「量子コンピューター」の回がこの後1:20からNHK総合で再放送するようなので、本放送を見たときの自分の感想を改めてここにまとめる。
一般のメディアにおける「量子コンピューター」の取り上げ方はいつも、専門知識を持っている人間から見たらとんでもない誇張と飛躍で充ちている。もはやSTAP細胞詐欺か何かに近い危険性を感じるので、こういう話に接する時の注意点、「ここを省略していることに気づくべき」要点を解説する。
メディアにおける「量子コンピューター」の説明は、大体いつもストーリーが似通っている。
件の軽い調子の番組だけでなく、ニュートンだろうと日経サイエンスだろうと、まあおおよそ複素関数論の「ふ」の字も紙面に出したら読者がついてこれなくなる程度のメディアではほとんど同じ構成である。
これはこの20年ほど変わらない一種のパターンになっているが、実はこのそれなりに繋がっているように見える一行一行の行間すべてに論理的な問題を孕んでいる。
この行間に実は存在する論理の省略、あるいは嘘と言っても良い誤摩化しをひとつひとつ指摘していこうと思う。
量子ビットには重ね合わせの状態が保持できる。これに対して計算処理をすれば、重ね合わせたすべての状態に並列に計算を実行できる。ように見える。
しかし、これも一般的に聞いたことがあるはずなので思い出して欲しいが、「量子力学の重ね合わせの状態は、『観測』により収束する」。
つまりどういうことか？ 量子ビットに対する処理が並列に実行出来たとしても、量子コンピュータの出力はそれをすべて利用できるわけではない。
量子コンピュータの出力とは、量子ビットに対する並列処理の結果の、確率的な観測に過ぎない。
なので、手法的な話をすれば、量子アルゴリズムとはこの「確率（確率振幅という量子状態のパラメータ）」を操作して、望む入力に対する結果が観測されやすくする、というちょっとひとひねりした考え方のものになる。
単に並列処理ができるから凄いんだという説明は、増田自身一般向けの説明に何度も繰り返したことがあるが、まあ基本的には素人相手の誤摩化しである。
ここさえ踏まえれば、知識がなくともある程度論理的にものを考えられる人には、量子コンピュータに対する色々な期待も「そう簡単な話ではない」となんとなく感じられると思う。
量子コンピュータのキラーアプリとされている暗号解読は「ショアのアルゴリズム」という非常に巧妙な計算を通して得られる。
上で説明したように、量子コンピュータは単に「並列計算だから」なんでも高速な処理ができる訳ではない。暗号解読については、この「ショアのアルゴリズム」という自明でない計算手法（高速フーリエ変換の応用）が見つかってしまったからこそ問題になっているのであって、このアルゴリズムの実行が出来なければ暗号解読ができるとは言えない。
さてここからは量子力学というより計算機科学の話になるが、あるチューリングマシン上のアルゴリズムが別の計算モデルで実行可能かどうかは、その計算モデルがチューリング完全であるかどうかによるというのはプログラマには常識である。
これは量子コンピュータにおいても変わらない。量子コンピュータの一般に知られる多くのアルゴリズムはドイチュの量子チューリングマシンを前提に作られており、チューリング完全でないアーキテクチャでは実行できない。できるはずがない。ショアのアルゴリズムも当然そうだ。
しかしながら、この20年弱、D-Wave社が最初の「自称・量子コンピュータ」を開発したと発表して以来、さまざまな企業が「開発に成功した」と発表した「量子コンピューター」の中で、このチューリング完全なものは何一つ存在しない。
これらでは、今後どれだけ「性能」が伸びようとも、暗号解読の役には立たないのである。
以上の議論から総合すればわかると思うが、量子コンピュータで世界が一変するなんてヴィジョンははっきり言ってSF以下のファンタジーというレベルでしかない。
第一に、量子コンピュータの利用できるドメインは非常に限られたものであるし、第二に、その中の最も宣伝されているものである暗号解読の可能な量子チューリングマシンの開発の目処などまったく立っていない。どころか、業界のほとんど誰も挑戦することすら本気では考えていない。
現状の「自称・量子コンピュータ」（量子情報システム、とでも言おうか）にも利用の可能性はある。何より量子状態そのものが作れるので、物理学や化学領域の量子システムをシミュレーションするのに適しているのは言うまでもないだろう。しかし、まあ、現状あり得る比較的現実味のある用途というのは、それくらいではないか。
このように、メディアが量子コンピュータについて語るとき、そこには非常に多くの誤摩化しや飛躍が含まれる。これは結構業界の根幹に関わる問題なのではと思うが、時間が来たので総括は後述にでもすることにする。
何か質問があればどうぞ。
コンピュータ・サイエンスで取り組まれている問題の一覧を紹介しよう。
その目的でわざわざ任意個で定義するの無駄に難しくなるだけで何で？って意味わからんかったのに、何か方針でもあるのかと思ったら途中で急に2個になって、昔研究室とかにいた無駄に話が長くて問題を難しく見せようとする馬鹿ってだいたいこんな感じだったなって思い出したわ
文面から滲み出るこのくどさと馬鹿っぽさは昨晩増田書いてたチューリングマシンがどうだの言ってる奴と同一人物なんやろなと勝手に思っている
とある高名な環境建築家（YouTubeに動画も上げている）が省エネ建築の経済的・社会福祉的合理性を説明するときに、「ちゃんと計算すれば小学生でもわかる（のに、相応の地位にいる人がいい加減なことを言うのはけしからん）」という言い回しを多用する。
いや、実際のところ、自分にとってそれは余りにも耳慣れたフレーズのため、特に気に留めるほどのものとも思っていなかったのだが、ある動画に「小学生だとか人を馬鹿にするような言い方はやめろ」とクレームがついていて驚いたのだ。
それなりに整った環境で理系教育を受けたものにならわかると思うが、「研究発表は『頭のいい小学生にならわかる』ようにせよ」というのは誰がいつ言い出したかもわからないくらいあまりにもそこら中で聞く言葉で、これを特に何かを見下したとか馬鹿にした言い方だと思う奴はいない。
何故ならば、ここで言う『頭のいい小学生』は『特に専門知識はないが理解力は深い人』を意味するのであり、具体的には『専門分野の違う他ゼミの教授陣』のことを指すからだ。
これが「人を馬鹿にした言い方」だと思う時点で驚き、非アカデミックなキャリアを詰んだ人々との文化の壁をまずは思わざるを得なかったが、よく考えるとこれこそがつまり『理系』という知性の特殊性と汎用性を表す側面なのだと思うに至った。
『小学生』と比較されると、普通の人は怒るらしい。何故か。小学生を劣った存在だと思っているからだ。
この人たちにとって『小学生』と呼ばれることは『頭が悪い』とか『未熟』とかを意味するのだろう。
しかし、理系の認識においてはそんな意味合いはほとんどないと言って良い。
理系は思考力の学問なので、「知識がなくてもわかる奴には説明すればわかる」「わからない奴、考えようとしない奴はどれだけ本を読んでもわからない」という認識が当たり前だからだ。
これらの競技が若いうちに才能を発揮できなければ辛いと言われるように、数学や物理の仕事も若いうちにできなければその後もあまり希望はない。
若さは可能性ではあってもなんら見下す要素ではないのが理系の世界だ。
さらに考えを深めてみよう。
将棋や囲碁は、ルールはシンプルだが組み合わせが複雑で、知識より思考力がいるものだというのは誰にでもわかる。
しかし数学や物理は難しい数式や抽象的な概念を覚えなければいけないから、小学生に難しい問題は理解できないはずだ。と、考える人も多いかも知れない。
だが実のところそれ自体、そんなことはないと証明されているのだ。
チューリングマシンという概念がある。イギリスの数学者アラン・チューリングの考えた計算モデルで、現在のコンピュータの元になっている。
さて、ではなぜチューリングマシンは「コンピュータの元」たりうるのか？ 言い換えれば、「チューリングマシンには何ができることが保証されているのか」？
この答えが、まさに「理系の議論に『小学生にもわかる』説明を義務づけることができる理由」である。
チューリングマシンは、本来ただの計算機のアイデアではない。それは『数学自体の定義』である。
『計算とは何か』『計算できるとはどういうことか』この答えを探した結果チューリングが得たのが、『計算とはチューリングマシンで解ける問題のことである（意訳）』という、現代ではもはや計算の定義、数学の定義として認められている回答である。
計算とはチューリングマシンで解けるもののことなので、どのような数学的問題もコンピュータのプログラムとして書き、計算することができる。
コンピュータのプログラムとは、ifとgotoを伴った算数レベルの計算の連続のことなのだから、これはつまりどのような数学的問題も、深い思考力さえあれば『算数』レベルの説明に落としこんで理解できることを意味する。（方程式がなくても鶴亀算が解けるように。）
ここで必要なのは、純粋に算数程度の知識と、それを深く複雑に組み合わせる思考力だけである。
従って、理系の説明、数学的に表される定量的な議論というものは、説明者にきちんとした理解があれば必ず算数レベルの話に落とし込める。
最近は、ネットの声の大きいマナー講師たちによって「専門的なことを誰にでもわかるように説明することなんてできない」という言い訳を聞くことが多いが、少なくとも理系の問題において、定量的な議論をする限りは、『数学』は『算数』の複雑化、抽象化に過ぎないのであり、必ず噛み砕いて説明することは可能だ。
ただし、ここで聞き手に求められるのは、何をおいても『算数レベルでならしっかり理解できる知能』ということになる。
つまり『頭のいい小学生』には必ず理解させられても、算数すら苦手な『馬鹿な大人』に希望はないということである。
『小学生でもわかる』は、小学生を劣ったものと考えている言葉では決してない。しかし、それ故にこそ、小学生レベルの算数も覚束ない大多数の大人が、劣ってるどころではない論外の存在であることを突きつけてしまう厳しい言葉なのだ。使い方には気をつけなければいけない。と思った。
お前らはAI以外の科学研究分野になんて興味もないから知らないんだろうが、この業界には「もはやだれもできると信じてないけど、政治的にやり続けなければいけない研究」というものがある。
量子コンピュータがそうで、20年前には「無理。できない。ほぼ間違いなく」という答えが出てる。
それでもなぜ研究を辞められないか？ 「ほぼ」でなく「絶対」でない限り、もし万が一にも億が一にも「敵対勢力」に先に開発されたら安全保障に重大なリスクが出るから、というだけの話だ。
違うのは、これらがある程度の結果にたどりつくことで開発競争にもケリがついたことと違って、量子コンピュータはどこまで行っても何にもならないから、ただ無駄に研究費を食うだけなこと。
成果が出ていると強弁するために、「量子超越性」などと20年前はなかった概念が作られた。しかし、今量子コンピュータと呼ばれているものは、20年前に量子コンピュータと呼ばれていたものとは全く違う。
具体的には何が違うか？ 今の自称・量子コンピュータには「暗号解読」なんてできない。何もできない。
何もできないのに何かをやっていると主張するために「超越性」などという何の根拠もない言葉で誤摩化している。
専門外なので推測だが、「常温核融合」や「常温超伝導」も似たような状況なのではないか。
量子コンピュータの場合、先に開発した方が情報・通信セキュリティの覇権を握る絶大な武器を得る。
常温核融合や常温超伝導も、エネルギー利用に革命的な変化をもたらすのだから、勿論軍事上の脅威になるだろう。
そういう技術は、たとえ「ほぼ無理」でも開発を辞めることはできない。「絶対無理」を誰かが証明でもしない限り。
AIがそういう技術に当たるかと言えば、それはその可能性はあるだろう。膨大な生成情報によるネット情報の攪乱はセキュリティ上のリスクになり得る。
お前たちが量子コンピュータの可能性をいつまでも信じ込まされていつか何かになると思っているのと同じように、AIも（仮にどこにもたどりつけないとしても）そういう立場を失うことはないだろう。
反AIでもなんでも良いが、それぐらいの現実感覚は持たないで空回りしているのは傍から見ても忍びないぞ。という忠告。
大学院まで専門にしてても就職で全然違うところにいくなんてよくあることなんだがそんなことも知らないのか低学歴はw
量子ゲートが云々とかそれこそ素人向けメディアの受け売りばっかで量子チューリングマシンも知らないやつがどの面下げてと
って話をしてるの
エンタメはかなり少なかった
たとえばイミテーションゲームは結構エンタメ感あったよね、チューリングマシンは直接ひと殺してないからね
文脈としては、オッペンハイマー周りのゴタゴタ（たぶんアメリカ人的には散々擦られた話）がメインの映画だった
登場人物の紹介がほぼされないので、その膨大な前提を知らないと展開の6割は付いていけない
ある程度原爆周りの話は知ってたつもりだったけど、レベルが足りなさすぎた
オッペンハイマーの生涯が知れる〜という感じでもなかった
何ならオッペンハイマーはスパイだったのか？あたりの掘り下げが5割だったんじゃいかな
登場人物がとにかく多い、覚えるべき人物だけで15人超えてると思うんだけど、それ以外の覚えたほうが良いのかな？なモブが30人は居る
面白くないとは言わないし、あまり居なかった主人公だし、意義もあるしよくやったと思うし、シンゴジ好きな人とかには受けそう
そんな作品
理解を助けるためのわかりやすくする仕掛けみたいなものもかなり少なかった
これはクリストファー・ノーランらしい、悪い意味で
時系列がね、3・4本くらいあって行ったり来たりしてるの、最初どの順で起きたのかわからなくて混乱した
これも史実を元にしてるから「このシーンは知ってるよね」で描かれてる気がする
あと長い、そして濡れ場ががっつりある
＿＿＿＿
それでこれバズってたのか
https://note.com/dj_gandhi/n/ncf406716af1f
原子力委員会の偉い人
オッペンハイマーを所長に抜擢した人
なんか対立してる
マジこいつは途中で「誰だっけ？」ってなる
今見終わって調べても「で、誰だこいつ？」ってなるね
3周してもわからんかも
やっぱ物語の描かれてない部分が多すぎて、三国志とかそういう感じになってる
苦手
基本情報・応用情報試験みたいなのとか、CPUの仕組み、コンパイラの実装、分散システムやデータベースとかそういうエンジニアリングガチ勢みたいなのをイメージして大学でCSを学ぶとけっこうショックを受けるぞ。
俺の知ってるCSは、チューリングマシンの表現能力とか停止性問題とかYコンビネーターとかチャーチ数とかの世界で、コンパイラといってもε-CLOSUREみたいな話をじっくりやる感じ。
具体的な話が全然出てこない数学の一ジャンルってイメージかもな。
競技プログラミングみたいなアルゴリズムもそれほど時間をかけない。ベイズ推定をギリやるかどうか。
そういう知ればすぐ身につくものよりも、めちゃくちゃ考えて濃厚なパラダイムを時間をかけて吸収するような学問だった。
で、そんなCSを学んで直接役に立つのは多くの人の場合計算量のオーダーとかくらいかも。
モナドみたいな概念に抵抗なくなるとか、ラムダ式の意味を深く理解できるというのもあるけど、それSIとかWebやスマホアプリの開発業務で必要かというとね。
賢い人は、ちゃんとSNSのユーザー同士の関係性とかレコメンデーションみたいのにもCSの知識を応用できると思うけど、一般人は賢い人が作ったライブラリを使う側だよね。
チューリングーッス
パソコンとか、スマホとか弄っているとじゃあ元となったものはなんだろうと考える訳ですが、そこでよく出てくるのがチューリングマシンのお話だったりします。
まぁ実際に使ったことがないのでなんの機械かわかっちゃないんですが
実は僕らのスマホも超高性能なチューリングマシンなんですわって言われても意味わかんないですよね、0と1以外にも入力できている訳だし、めっちゃいろんな動画とか見れる訳だし
でも無茶苦茶基本に立ち返ると0と1でなんとか頑張ってるらしいです。そのなんとかがあまりにも高速かつ膨大すぎて、遠くからフィルター越しに見たそれに模様や色がついてるように見えるだけで。まぁフィルター越しに見たら何でも色は付くか。
上手いこと色を呼び出したり、画像を呼び出したり、ブラウザを呼び出したりしながら面倒な処理の簡略化を何度も何度も経て今に至る訳で
それでも大昔の0と1の入力に対する試行錯誤があったから、今こんな風に真偽不明な話をできてる訳ですね。増田の話は信じすぎるな。
謎の究明よいか！謎の究明ヨシ！
すまん、バカで。
現時点でも将棋とか特定の用途に用いる人工知能は学習を繰り返してプロより強くなってしまうわけで、汎用人工知能となると、多様な用途それぞれについて学習を繰り返して日々賢くなっていくのだろう。
その前提の、変化しないものが我々の対処すべき問題で無いんじゃ？、って話をしたい。
おそらくご存知だろうが、将棋も囲碁も無限にはパターンがない。組み合わせは、有限のはずだ。そりゃ、コンピューターには可能だろうけど、世の中が対処しないといけない問題は有限でなく、無限であるならば、解決すべき問題はチューリングマシンといった機械の上で対応できない問題な可能性があって、それは人工知能で対処できないのではないだろうか？という「P≠NP」の疑問をしたかった。すまん、説明不足で。
確かにいま主流の計算機が「ノイマン式コンピューター」なのだけどさ、チューリングマシンには記載できていない問題があることを知ろうよ。例えばさ、チューリングマシンが事実であるとしても、そこには CPU の周波数が原因となる時差が生じることによるラグがあって、そのことを感覚的に知覚してないとコードできない事例もあるのを知るべきだと思うよ。人工知能を作ろうとする場合には、統計学的な手法や、脳の仕組みを真似たものと色々あるわけだけど、究極的にはアセンブリで動くものになるのだったら、計算機の特性による歪みが反映されるはずではないのかい？今の人工知能は半精度を多用する場合が多いけど、二進法と十進法の変換ミスによる理想と現実の乖離は無視できるのかい？本当に我々の思考は「数学的なもの」で成り立っているのかい？もしそうだったら、どうして我々は計算ミスをするのだい？僕は不思議に思います。だから、数式と計算機は別物だと考えておくべきで、計算機科学も物理学と同じで「己の正しさを示すだめだけに数学を使う」学問で良いのじゃないでしょうか。
昔はプログラムはパンチカードに穴を開けてそれを読み込ませて実行してたんだよ。
UI は紙。
昔の映画で科学者がパンチカードの紙を眺めてるのを見たことない？
このまとめ↓みたいな感じ。
https://togetter.com/li/1317261
あと、今ほどいろんな処理をしてる訳ではないし、CPU の命令セットも少ないから、そこまで大変だったわけではないと思うよ。
雰囲気だけなら brainfuck をやってみると感触をつかめるかも。brainfuck はよりチューリングマシンに近いシンプルな言語。hello world くらいならすぐに書けるよ。
あとはそれを0か1かで表現してパンチカードに穴を開けるような感じだと思う。
https://ja.m.wikipedia.org/wiki/Brainfuck
というわけで、釣りっぽいけどあえて書いてみた。
チューリングマシン(http://www.nicovideo.jp/watch/sm22082958)だったり、ハーモニックドライブ（http://akiyuki.jp/works/573）だったり、ライフゲーム（http://www.nicovideo.jp/watch/sm19347846）だったり、面白いことやっている人いるなーと目についていたのだけど、今何処にいったのか。
