人気ブログランキング | 話題のタグを見る

Q150の解答(式で書く)

(a)
G=Q#Q#
つまり、Qの不動点とする。定義により、GとQGは同値となる。

G=T⟷SnG=T⟷Q’G=T⟷QG=F
QG=Q(Q#Q#)=Q#Q#=G
なので、
G=Q#Q#=T⟷QG=Q#Q#=F
Gは決定不能となる。

(b)
(a)によりG≠T⟷∀n ¬(SnG)=T⟷∀n (SnG)=F⟷Q’G≠T⟷QG≠F
GとQGは同値なので、QGも決定不能となる。
by tomoarrow | 2015-09-12 07:00 | モチーフについて | Comments(0)