1. 決定可能、半決定可能の違い、Aの決定可能性、Aの半決定可能性、 Aの半 決定可能性の、実際にありえる組合せとそうなる理由を述べよ。
2. Turing機械の停止性問題が決定不可能であることを証明せよ。
3. 授業あるいは自分で勉強した計算機に関することで、一番興味を持ってい ることについて解説せよ。ただし前期レポートとは異なること。
4. 条件部に否定が入ってもよいように拡張したPrologのプログラムで、述語 を次のような2つのグループに分けることができるようなものを考える。2つの グループをA,Bとすると、(1)AからはBの述語を条件部で使用していない。(2)A 同士あるいはB同士の述語はそれぞれの条件部で否定を伴って現れない。この とき、プログラムの意味を、最小不動点の理論を用いて与えよ。(ヒント:Aの みで考えると、否定を用いないPrologプログラムであり、通常通り意味を付け られる。その後、Bの意味をつける。)
5. プログラミング言語を適当に設計し、その表示的意味論を与えよ。
6. 授業に対する感想、批判、改善点。
提出先:
電子メール sakura@i.h.kyoto-u.ac.jp
あるいは A304 桜川
提出期限:1月21日多少の遅れは認めるのでめげずに出すこと
電子メールで提出すると
として評価します。電子メールで提出でき
ない場合は、ワープロの出力でも同等とみなします。その旨を書いて下さい。
両方とも利用できない場合、
の評価がほしい人は、A304,A288まで相
談に来て下さい。