1. テープの記号列をコピーして2重化するTunring機械の構成方法を述べよ。
2. 決定可能、半決定可能の違い、Aの決定可能性、Aの半決定可能性、 Aの半 決定可能性の、実際にありえる組合せとそうなる理由を述べよ。
3. Turing機械の停止性問題が決定不可能であることを証明せよ。
4. 授業あるいは自分で勉強した計算機に関することで、一番興味を持ってい ることについて解説せよ。ただし前期レポートとは異なること。
5. 否定の入ったPrologのプログラムの意味を、最小不動点の理論を用いて与えよ。
6. フラクタル図形を選び、コンパクト・ハウスドルフ空間の空でない閉集合 全体の成すCPOの連続関数の自明でない最小不動点として表せることを示せ。 ここで自明でないというのは、連続関数による空間全体の像そのものがその図 形にはなっていないという意味である。
7. 授業に対する感想、批判、改善点。
提出先:
電子メール sakura@i.h.kyoto-u.ac.jp
あるいは A304 桜川
提出期限:2月3日(電子メールの場合は2月5日) 多少の遅れは認めるのでめげずに出すこと
電子メールで提出すると
として評価します。電子メールで提出でき
ない場合は、ワープロの出力でも同等とみなします。その旨を書いて下さい。
両方とも利用できない場合、
の評価がほしい人は、A304,A288まで相
談に来て下さい。