ウィリアムのいたずらの開発日記

ウィリアムのいたずらが、コンピューター関係について、思ったことを好き勝手に書いているブログです。

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

2017-08-05 19:16:21 | Weblog
8月5日

数学基礎論 サマースクール2017


の1日目を聞いてきた!ので、メモメモ




数学基礎論 サマースクール2017

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

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

 計算:コンピューター?
  →1930年代ころからの概念
 計算機:40年代から→計算機の歴史とともに発展
  数学系と情報系
 現実の計算機の仕組みにこだわらない

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

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

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

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

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

 問題は、無限個ある

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

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

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

 有限状態機械の限界

 aとbからなる文字列で、左から3文字目がa
 aとbからなる文字列で、右から3文字目がa
  →3文字すべての可能性をしめす 8とおり はじめbbb
   その間をa,bの線を引いていく
 ※まえに5文字にしたら、授業が終わらなくなりました(^^;)

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

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

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

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

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

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

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

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

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

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

 チューリングマシンの→

 ----->
 a C右  a とき、Cを書き、右に行く

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

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

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

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

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

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

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

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

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

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

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

 決定する
  真であるとき受理する
  偽のとき受理せずに停止する(ループX)

 決定可能
  LもLの補問題(文字列の補集合)も認識可能
  可能=する機械が存在する
  認識可能(再帰枚挙可能RE)、(計算枚挙可能CE)

・問題U
  入力 機械Mと文字列xの組
  答え Mはxを受理するか

 つまり、 U(M,x)
  真 Mがチューリング機械を示しておりそれがxを受理するとき
  偽 それ以外のとき
 Uは認識可能:Uを認識する機会を万能チューリング機械という
   足し算をする機械
   掛け算をする機械
   問題Lを認識する機械
 →Uを認識する機械を万能チューリング機械ともいう
 Σ、Γ、Q、開始状態、受理状態、遷移規則
  →これをMとする
 Uを認識する:機械の動きの定義に従って調べればよい

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

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

ジャンル:
ウェブログ
この記事についてブログを書く
この記事をはてなブックマークに追加
« YAMAHAのFM音源チップがMaker... | トップ | ミルフィーユシステム »
最近の画像もっと見る

Weblog」カテゴリの最新記事