P181-P191
コンピュータ科学を学ぶ理由について
- 再利用
実変数の複素または実数値函数を別の同種の函数に写す変換 フーリエ変換 - Wikipedia
- 量子力学との比較
コンピュータ科学者の思考を学ぶ
計算モデル
アルゴリズム(プログラミング技術から離れて存在する)
チューリングの登場、1930年代になってから計算の近代的理論が導入された
すべての数学的問題を解くことのできるアルゴリズムは「存在しない」
計算理論に対する2つのアプローチ
- Turingによって提唱されたもの
- 計算の回路モデル
特定の問題に対して異なる複数のアプローチ
チューリング機械
- プログラム
- 有限状態制御(CPUに相当)
- テープ(メモリに相当)
- 読み書き用テープヘッド(ポインタに相当)
状態q1→qn(n個) 状態を大きくしても劇的には改善しない
レジスタなどが一定以上増えても性能向上には寄与しない
有限状態機械を考える良い方法
- qs qh
- q1からqnまでの状態があったとき、qs qhという特別な状態がある。
- qsがプログラムのスタート、qhがプログラムの停止(hold)
チューリング機械のテープは一方向に無限に伸びている テープ区画(=メモリのアドレス)に0,1,2,3といった番号を割り振る
0か1かbしかない機械を考える。(0は左端)
テープの長さは無限で、0か1かの情報が入っている部分は有限。(概念上は無限だが、使われている部分は有限)
プログラムにしたがって1ステップずつ従っていく。
プログラムはq, x, q', x'
実行 テープヘッドを左へ右へずらしながら実行していく。
プログラムはひとつらなり。 これらはプログラムの実行により状態が変化していく。
<q, x, q', x'> <q, x, q', x'> <q, x, q', x'> <q, x, q', x'> <q, x, q', x'>
enumでこの中のどれかであること、今指しているのがコレ。みたいなやつ。=二重の条件のパターンマッチ。
内部状態 q1...qn 特別な状態 qs qh 今指し示しているxの中身を変えて、テープの位置を右か左にずらす。例外はテープの左端にあるときテープをさらに左にしようとするとプログラムは停止する。
テープの左端はアドレス0であって、テープの途中から左端が始まるわけではない。
qs q1 q2 q3 qh
0 or 1 or b(lank)
複数セルが0 1 0 1みたいな感じで続いている
チューリング機械は負でない整数から負で整数を出力するようになっている。
f(x) = 1を計算するだけでもものすごい力がいる。 が、理論上チューリング機械を使えばあらゆる数学的問題を解決することが可能となる。(ただし実行効率は度外視している)
チューリング機械によって計算可能な関数とアルゴリズムによって計算可能な関数が等価であるとチューリングは主張する。
数学で厳密に特定できることがわかったことが大きい。
70年以上たってもチューリング機械が計算出来ない問題があることは証明されていない。(エミュレートしようとして出来ない)
- 量子コンピュータで計算できない≠チューリング機械で計算できない
- 量子コンピュータで計算できる≠チューリング機械で計算できる
コンピュータはユニークなIDをふれる
量子コンピュータはチューリング機械は同じく数学的な問題を解決することが出来る。 量子コンピュータによってチューリング機械よりはるかに効率的に計算できる問題もある。
高次の擬似コードを使う。
例。brainfuckはチューリング完全
チューリングモデルのいかなる側面も変更できない。
テープが2つあるチューリング機械があるとして
単一テープのチューリング機械との違いは、プログラムが違うこと。
でも、チューリング機械は同じ計算結果が得られる。
コインの裏表でテープの値を変える
- 計算可能な関数のクラスは変化しない
- モンテカルロ法、遺伝的アルゴリズムのようにより効率的に計算が出来る可能性はある(ただし最適解ではない)
数学のすべての問題を決定するアルゴリズムは存在するか？
No.
たとえば、トポロジー空間がトポロジー的に等価であるかどうかを決定する問題は決定不能
訳が雑
普遍的チューリング機械
M(x)=x
近代的なプログラム可能なコンピュータと同様な考えにそっている。 命令の並びを変えれば何でも出来る。 CPUの命令セット
１台の機械によってあらゆる問題を計算できるマシンが存在しうる。
停止問題
チューリング数xを有する機械は数yが入力されると停止するか？この問題を解決するアルゴリズムは存在しない。(所謂背理法、自己言及のパラドックスで証明出来る)
回路モデル
- 論理ゲート
- 入力ビット
出力ビット
0→1→0→1を繰り返す
- ハングアップもあり得る
- ループがないとメモリは作れない
組み合わせ回路
回路に内部状態のことは考えない
- and
- or
- xor
- not
これらを組み合わせることで、様々な計算が出来る。
少数の決まったゲートだけを使って任意の関数を計算できる。
f(x)
f0 = f(0;x1,.....,xn) f1 = f(1;x1,.....,xn)
1.wires 2.ancilla bits 3.the FANOUT operation 4.the CROSSOVER operation 5.the AND,XOR,and NOT gates
quantum
qubit 量子ビットは、情報のコピー(クローン)が出来ない。コピーしたらオリジナルは、死ぬ。
nand回路があれば他の回路を表現できる。
3bitの回路を計算するのに5bitの回路でも10bitの回路でも構わない。
計算問題の解析
- 計算問題とはなにか(決定問題)
- 与えられた問題をとくためのアルゴリズム
- 与えられた計算問題をとくために必要な最小限のリソースとはなにか
(アルゴリズムの設計についてはこの本では扱わない)
計算リソースの定量化
O(n)
compare and swap コンペア・アンド・スワップ - Wikipedia
小並感
難しい。ので、ブルーバックスからやり直そうと思う。
