Hatena::Groupxn--272ax3f

論理と計算のしくみ4.1と4.2

論理と計算のしくみ4.1と4.2

プレゼンテーション

チューリング機械

  • (無限の)テープ
  • (テープのマス目を読む)ヘッド
  • 現在の状態
  • テーブル

テープ

  • テープに印字できる文字全体
    • テープ・アルファベット
    • ''(空白文字を含む)

ヘッド

  • ヘッド下にあるセルに対して
  • マス目の文字を読み取る事ができる
  • マス目の文字を書き換えることが出来る

状態

  • 有限種類の状態を持つ
  • 状態集合
  • "現在の状態" をひとつだけ記憶できる
  • 初期状態, 終了状態 を持つ
    • 初期状態から始まる
    • 終了状態に至ったら停止

テーブル

  • 入力
    • 現在の状態
    • ヘッド下のマス目の文字
  • 出力
    • 次の状態
    • ヘッド下のマス目に印字すべき文字
    • ヘッドを右か左に動かすか、又は動かさないか

条件

  • 状態集合、テープ・アルファベットは有限
  • 現在の状態とヘッド下のアルファベットの組み合わせも有限
  • テーブル(プログラム)も有限
  • テープは無限だが、テーブルは有限
  • テープも有限時間内に参照できる部分は有限

計算可能関数

  • 自然数の計算なら、アルファベット {0,1,''} で出来る
    • 入力 初期状態でのテープの先頭の2進数
    • 出力 終了状態でのテープの先頭の2進数
  • 終了状態に至らない場合は未定義

帰納的関数

  • 原始帰納
  • 部分機能的

原始機能的

次の規則を有限回適応して定義できる

  • 定数 0 は 0 引数関数として原始機能的である
  • S(x) = x + 1 と定義される関数 S は原始機能的 (後継者関数)
  • f(x_1,...,x_n) = x_i と定義される関数  f は原始機能的

原始機能的

  • f, g_i が原始帰納的である時
    • h(x_1,...,x_n) = f(g_1(x_1,...,x_n),...,g_m(x_1,...,x_n))
    • h は原始機能的 hfg_i の合成

  •  plus(0,y) = y
  •  plus(S(x),y) = S(plus(x,y))
  •  f(x) = x
  •  plus(S(x),y) = plus(x+1,y) = x + 1 + y = plus(x,y) + 1 = S(plus(x,y))
  •  plus(S(x),y) = S(x,plus(x,y),y) ?
  • 同様に  xy x^y も原始機能的

原始帰納法

  • という自然数帰納的定義に従って関数を定義することに他ならない
  • よって原始機能的な関数は明らかに計算可能 (本当?)

有界最小化

  •  f(x,y) が原始帰納的関数のとき、次のような g(x,z)は原始機能的
  •  y < z かつ f(x,y) = 0 を満たす自然数 y が存在するとき, g(x,z)はそのような yの最小のものに等しい(最小化ということ)
  •  y < z かつ f(x,y) = 0 を満たす自然数 y が存在しないとき, g(x,z) = 0となる。zはyの上界を示している。この場合 g(x,z)の値はなんでもよいがとりあえず 0

有界最小化

  •   h(x,z,0) = 0
  •   h(x,z,S(w)) = (1 \dotdiv f(x,z \dotdiv S(x)))(z \dotdiv S(w) + ( 1 \dotdiv (1 \dotdiv f(x,z \dotdiv S(x))))(h(x,z,w))
  •   h(x,z,S(w)) = if f(x,z \dotdiv S(x)) = 0 then f(z \dotdiv S(x)) else h(x,z,w)
  •  f(x,z \dotdiv S(x)) が 0より大きく1未満だと問題なきが

有限列の符号化

  •  p(x,y) = div2((x + y + 1)(x + y)) + y
  •  p_1(p(x,y)) = x
  •  p_2(p(x,y)) = y
  •  <x,y> に対して自然数  p(x,y)  <x,y> の符号
  •  <x,y> p(x,y) を対応させることを符号化

符号化

  •  p(x,y) を繰り返し適応すれば
  •  p(x_0,p(x_1,...,p(x_n-1,0))) と有限列  x_0, x_1,...,x_{n-1} を符号化できる
  • 復号
  •  b(y,0) = y
  •  b(y,S(i)) = p_2(b(y,i))

と定義すると

  •  a(y,i) = p_1(b(y,i))

と定義されるa(y,i) は 有限列  x_0, x_1,...,x_{n-1} の 符号 yに対して  a(y,i) = x_i を返す

自然数の順序に従った帰納法

  •  h(x) = c (f(x) = 0)
  •  h(x) = k(x,h(g(x))) (f(x) \neq 0)

と定義される関数は原始機能的、ただし c は自然数で [tex: k(x,y) は原始帰納的関数

  •  div2(x) = 0  (f(x) = 0)
  •  div2(x) = div2(x \dotdiv 2) + 1 (f(x) \neq 0)

h(x) と h'(x) がよくわからん

部分的機能的関数

  •  f(x,y), g(y) を原始帰納的関数とする。自然数から自然数への部分関数h(x) を次のように定義する。
  •  f(x,y) = 0 を満たす自然数yが存在するとき、そのような y の最小のものを  y_0 とし、 h(x) = g(y_0) と定義する
  •  f(x,y) = 0 を満たす自然数yが存在しないとき、 h(x) = \bot と定義する

このように定義できる部分関数 h(x)を部分帰納的という

最小化

  •  f(x,y)自然数 xに対して f(x,y) = 0を満たす最小のyを求めることを最小化(minimization)という
  •  h(x) = g(\muy.(f(x,y) = 0))

帰納的関数

  • 最小化を何度適応しても、部分帰納的関数の範囲を超えることはない
  • 任意の自然数 x に対して  f(x,y) = 0 が存在するとき、つまり任意の自然数 xに対して、 h(x) が定義されるとき、帰納的であるという

定理4.1

自然数から自然数への部分関数が部分帰納的で有ることと、チューリング機械によって計算可能であることは同値

このへん端折ってる

停止問題

チューリング機械 M のインデックス e と 入力 x に対して

 h(p(e,x)) = 0 (T(e,x,y) = 0 を満たす自然数 y が存在する)

 h(p(e,x)) = 1 (T(e,x,y) = 0 を満たす自然数 y が存在しない)

を満たすような h は計算可能であろうか。 M, e, x が与えられた時、停止するか判定できるか?

答え

判定できない

帰納的集合

 f(x,y) が原始帰納的な関数であるとき

  •  R = {x \in N | f(x,y) = 0 を満たす y \in N が存在する }

によって定義される N の部分集合 R を帰納的に可算であるという

  •  R = {x \in N | h(x) \neq \bot}

R と N - R の両方が帰納的に可算な集合であるとき集合R を帰納的であるという

  •  R = {x \in N | f(x,y) = 0 を満たす y \in N が存在する }
  •  N - R = {x \in N | s(x,y) = 0 を満たす y \in N が存在する }

とすると任意の自然数x に対して

  • r(x,y) = s(x,y) = 0 を満たす自然数 y が存在しない
  • r(x,y) = 0 を満たす自然数 y が存在するか、s(x,y) = 0 を満たす自然数 y が存在する
  • 任意の x が R に 属するかどうか
    • y = 0 とおいて、r(x,y) と s(x,y) を解く
    • y = 0 で成り立たないなら y++
  • K は帰納的に可算だが、帰納的ではない
  • N - K は帰納的に可算でない N の部分集合