「はじめての計算可能性」を聞いてきた！

８月５日

数学基礎論　サマースクール２０１７

の１日目を聞いてきた！ので、メモメモ

---

数学基礎論　サマースクール２０１７

■ごあいさつ
・ことしは計算理論
　３つ
　　入門編
　　発展編
　　　チューリング次数
　　　ジェネリック次数
　　補講：同一性　ＨＦ

■はじめての計算可能性
・計算理論
　計算によって何ができるか・できないか
　　計算：与えられた手順に従った情報処理（アルゴリズム）

　計算：コンピューター？
　　→１９３０年代ころからの概念
　計算機：４０年代から→計算機の歴史とともに発展
　　数学系と情報系
　現実の計算機の仕組みにこだわらない

　抽象化された計算機を考え、それによっていかなる処理ができるかを調べる

・問題とは
　各入力に対し、答えが真か偽か定まったもの
　　入力は文字列であらわされる

　たとえば；
　　与えられた正整数が、素数か応えよ
　　与えられた文字列にabaが現れるか応えよ

　→いわゆる判定問題を扱う

　　普通のいいかたとちがう
　　　１５１７は素数でしょうか→入力
　　　１５１７は素数でしょうかは偽である→問題

　問題は、無限個ある

・機械でとく→機械
　　性質をみたす：受理
　　満たさない：不受理
　→有限状態機械
　　　二重丸：受理状態
　機械とアルゴリズム（算法）は同じ
　与えられるもの：無限
　機械：有限→状態は有限個
　→（遷移規則）も有限本
　　有限長の文字列（参譜：プログラム）で書き表せる

・有限状態機械の定義
　　有限個の状態の集合Ｑ
　　文字ｚの集合Σ
　　遷移規則
　　→受理
　(文字列はこの講義では、有限とする）

　解くとは
　　判定問題を解く
　　　真のとき受理、偽のとき受理しない
　状態数が最小のものというのは、定められる

　有限状態機械の限界

　aとbからなる文字列で、左から３文字目がa
　aとbからなる文字列で、右から３文字目がa
　　→３文字すべての可能性をしめす　８とおり　はじめbbb
　　　その間をa,bの線を引いていく
　※まえに５文字にしたら、授業が終わらなくなりました（＾＾；）

　与えられた文字列はaのNこ、bのNこという形か？
　　→この問題を解く有限状態機械は存在しない

　証明は背理法
　　状態は有限個なので、あるｍ≠ｎが存在して
　　　→鳩の巣
　　・・・

・計算の仕組み
　　ほかにもいろいろ・・・

　たとえば、左右に動けるようにしたら？
　（テープは両方向に無限）

　両方向有限状態機械
　　状態、受理、おなじ
　　文字：空白文字も含めるΓ
　　遷移規則がややこしくかわる
　停止する；計算終了

　能力変わらない
　問題Ｌを解く両方向有限状態機械が存在するならば、
　Ｌをとく有限状態機械が存在する
　→頑健な概念

　有限状態機械で解ける：正則な言語→正規言語：レギュラー

・強力なもの：書き込む能力を与える
　→チューリング機械：有限個に限らない・記憶できる書く能力を与える

　機械と状況があるとき→遷移規則→状況

　問題：与えられた文字列でaがbよりも多いか？

　チューリングマシンの→

　－－－－－＞
　a C右　　a とき、Ｃを書き、右に行く

　書き換えしない時は、同じものを書き、この場合、書き込み先の文字(上記Ｃ）を省略

　有限状態機械よりも、真に強力になった！

・チャーチ・チューリングのテーゼ
　チューリング機械で解ける⇔現実の機械で計算できる
　　　数学的にはっきり　　　　ぼんやりした主張

　→はまあよさそう（チューリング機械の動きは単純そう）
　←「計算」できることは、すべてチューリング機械でできるのか？

　ほかのいろいろなやり方で定義された計算可能性の概念とも一致
　　一般再帰関数
　　ラムダ計算

　※チューリングのころ、計算機はない→計算者と考えている
　
　でも、文字列に関する問題しか考えないの
　　→入力を符号化

　与えられたグラフがハミルトン閉路を持つか
　　グラフ：有限

　真か偽か応える問題だけっていうのは、どうなの？

　ちなみに、これらのもんだいを解く算法（チューリング機械）
　　与えられた正整数Ｘが素数か
　　与えられたグラフがハミルトン閉路を持つか
　　　→Ｎ個の並べ方N！とおりを全部調べる

・全部調べつくす：無限個の場合・・・
　「○○であるか」
　「○○でないか」
　ポスト(人の名前）の揃え可能性問題
　　　可能か→解ける
　　　不可能か→存在しないことが示せる
　揃え可能であることを認識する問題

　認識する
　　真のとき受理し
　　偽のとき受理しない→ループしててもＯＫ

　決定する
　　真であるとき受理する
　　偽のとき受理せずに停止する（ループＸ）

　決定可能
　　ＬもＬの補問題（文字列の補集合）も認識可能
　　可能＝する機械が存在する
　　認識可能（再帰枚挙可能ＲＥ）、（計算枚挙可能ＣＥ）

・問題Ｕ
　　入力　機械Ｍと文字列ｘの組
　　答え　Ｍはｘを受理するか

　つまり、　Ｕ（Ｍ，ｘ）
　　真　Ｍがチューリング機械を示しておりそれがｘを受理するとき
　　偽　それ以外のとき
　Ｕは認識可能：Ｕを認識する機会を万能チューリング機械という
　　　足し算をする機械
　　　掛け算をする機械
　　　問題Ｌを認識する機械
　→Ｕを認識する機械を万能チューリング機械ともいう
　Σ、Γ、Ｑ、開始状態、受理状態、遷移規則
　　→これをＭとする
　Ｕを認識する：機械の動きの定義に従って調べればよい

　→決定可能ではない
　　補問題が認識可能ではない
　　Ｕ＝
　　　　偽　Ｍがチューリング機械を表しており、それがｘを受理するとき
　　　　真　それ以外のとき
　　永遠に受理しないのか、時間がかかっているだけなのか？

　　Ｄばー（ｘ）　＝　
　　　　偽　Ｘがチューリング機械を表しており、それがｘを受理するとき
　　　　真　それ以外のとき
　　→対角線論法
　　　対角線を反転したものを考える。それは絶対ない
　　→補問題は認識可能ではない
　→決定可能ではない