書籍「計算できるもの、計算できないもの」 ノート

計算問題は3つに分類することができる

• 扱いやすい(tracktable)問題: 効率よく解く方法がある問題
• 扱いにくい(intracktable)問題: 効率よく解く方法がなく、現実的でない時間のかかる解法しかない問題
• 計算不能(uncouputable)問題: コンピュータで解けない問題

コンピュータプログラムとは何かということに対して、書籍内では3つの等価な答えを扱う。

• "チューリングマシン"による定義
• "Pythonプログラム"による定義
• "あらゆる妥当な"定義
  Pythonプログラムは等価なチューリングマシンを便利に表現する手段でしかないことを意識する。

還元

FとGの二つの問題があるとき、Fを解くためにGを解く必要がある(=Gが解ければFも解ける)とき、FはGに還元(reduce)されるという。

数学者は問題が易しいということのために還元を使うが、理論計算機科学者は問題が難しいということを示すために使う。

易しい問題であることを示すとは、ある問題Gが既に解けているとき、別の問題FがGの少しの変形を利用することで解けることを示すこと。

難しい問題であることを示すために使うとは、ある問題Gが計算不可能であることを示したい時に、既に計算不可能である問題Fがあれば、

1. FがGに還元されることを示す
2. Gが計算不能であるという結論を導く

という風に使うこと。

FはGにチューリング還元されるとき次のように書く

FがGより「小さい」問題であることを示していて、FはGよりやさしい(Gを解く方法が見つかればFを解く方法も見つかる)。

非決定性 (Nondeterminism)

マルチタスクの能力の特徴として非決定性という場合には、コンピュータが次に実行するステップが非決定的に決まるということを強調している。非決定性と決定性モデルでは計算能力は等価である。

非決定性のモデル

• スレッドの同時実行(本の中では主にこれを扱っている)
• 無作為行為
• 外部選択 (外部オペレータにより遷移が決定される)

非決定性チューリングマシン

決定性チューリングマシンの能力に加えて、必要なタイミングで自分自身のクローン(テープ・状態が全く同じチューリングマシン)を作れるチューリングマシンのこと。

非決定性を研究する理由

• 非決定性の視点から問題を解決する方が主張の証明が行いやすかったりすることがある
• 計算量理論で大きな成果をあげている。

有限オートマトン (Deterministic Finite Automaton)

テープへ書き込みができず、右にしか移動できないといチューリングマシン。決定的な決定性有限オートマトン(DFA)と非決定的な非決定性有限オートマトン(NFA)がある。チューリングマシンと同様、DFAとNFAは等価である。

正規表現 (Regular Expression)

正規表現はDFAと等価である。

チューリングマシンとの違い

チューリングマシンで決定可能なら決定可能であるということに対応するものがあり、DFAで判定可能なものは正規言語と呼ばれる。決定可能であるが正規言語でない言語が存在するため、チューリングマシンは有限オートマトンよりも強力である。これはDFAの「メモリ(記憶)」の大きさがDFAの状態数によって制限されるためである。