計算理論 期末試験
年
月
日実施
学生番号 氏名
を受理する状態数
以下の
の遷移図を求めよ
が帰納的でないとき
も帰納的でないことを証明する
空欄を埋めることで以下の 証明を完成させよ
なお
には 文章の説明 もしくは
の模式図を書くこと
は帰納的ではないが
が帰納的であると仮定する
このとき
を
が存在
する
この
を用いて 以下のような
を構成する
が
ことから
も
また
となるための必要十分条件は
である
なので
となる
つまり
は
を
よって
は
であるがこれは仮定に矛盾する
したがって
は
ではない
任意の二つの
½と
¾に対して
を以下のように定義する
½
¾
½
¾
½
¾
½
¾
このとき
が帰納的可算でないことを
を用いて証明する
空欄を埋めることで以下 の証明を完成させよ
が帰納的可算であると仮定する
このとき
を受理する
が存在する
この
を用いることで 以下のような
を構成する
の入力は
である
を入力
に対して動作させる
ここで
はすべての入力を受理しない
の符号化
である
が受理するならば
は受理し
が受理しないならば
は受理しない
であるための必要十分条件
は
となることである
したがって
は
を受理する
となる
ところが
は帰納的可算でないので
を受理する
は存在しない
この矛盾は
が存在するという
仮定から生じている
したがって
は帰納的可算でない
とし
の対応問題の実例を
½ ½
·
とする
このとき 以下の問に答えよ
½
·
となる文脈自由文法
½ ½に対 して
½を求めよ
¾
½
½
となる文脈自由文 法
¾ ¾に対して
¾を求めよ
上の
½と
¾を用いて 「
½¾か
」という問題が決定不能であるこ とを証明する
空欄を埋めることで以下の証明を完成させよ
½
の
·および
¾の
½
½
には 長さ の文字列が含まれていない
したがって
½
½
であることに注意すると
½
¾
となる
したがって
であるための必要十分条件は
である
の対応問題は決定不能である
ので 「
か
」という問題も決定不能である
問題の否定が決定不能である
ことと元の問題が決定不能であることは同値なので 「
か
」という問題の
否定である「
か
」という問題も決定不能で
ある
を
関数とする
任意の
½¾に対して
½
¾ !
½
!
¾
¼
½
!
¾
½
¾
!
½
!
¾
!!
½
½
!
¾
!!
となる
¼½が存在するような原始帰納的関数
から 原始帰納的関数
½¾が
½
¾
½
¾
½
¾
!
½
¾
½
¾
と定義されるとする
このとき
"¼½!に対して
½
¾
!
½
!
¾
!
½
!
¾
!
となることを
に関する数学的帰納法を用いて証明せよ
なお
関数の以下の性 質は証明無しに用いてよいが 用いた場合にはそれを明記すること
それ以外の
関数の性質を用いる場合には それも証明しないと不正解とする
ならば
ならば
なお 解答には次ページを使ってもよい
½ ¾ ½ ¾
½
¾
½
¾
½
¾
½
¾
½
¾
¼
½
¾
½
¾
½
¾
½
½
¾
½
¾
½
¾
½
¾
ならば ならば
