アーニーの機械は記号列を操作する機械で、ある記号列xを入力すると、ある記号列yをもたらす。いま、機械には2つの規則がある。2つの規則、規則Qと規則Cをあらためて見ておこう。
規則Q 任意の記号列xに対して、記号列Qxはxをもたらす。
規則C xがyをもたらすならば、Cxはyの随伴yQyをもたらす。
問題は以下の4問であった。
問１ それ自身をもたらすような記号列を見つけよ。
問２ それ自身の随伴をもたらすような記号列を見つけよ。
問３ それ自身の随伴の随伴をもたらすような記号列を見つけよ。
問４ 任意の記号列yに対して、ある記号列xで、yxをもたらすようなものが存在することを証明せよ。たとえば、どのようなxがAxをもたらすだろうか。
ここで、言葉で書いていくと文章が長くなりがちになるので、できるだけ記号を用いて表現したい。たとえば、「xがyをもたらす」というのを「x→y」と書くことにしよう。「もたらす」というのを「→」で表す。「x→y」のように記号で書いた表現を「式」と呼ぶ。そうすると、規則Qと規則Cの式はそれぞれ以下のように書ける。
規則Q Qx→x
（任意の記号列xに対して、記号列Qxはxをもたらす）
規則C x→yならば、Cx→yQyわかりやすくなるかどうか若干不安があるが、以降これでいこう。
（xがyをもたらすならば、Cxはyの随伴yQyをもたらす）
この書き方は『スマリヤンのゲーデル・パズル』には載っておらず、このブログでの表記だ。また、解答方法もなるべく本の解答方法とは違う書き方（僕が考えた方法）をしていこうと思う。
＊＊＊＊＊
問１ それ自身をもたらすような記号列を見つけよ。
（解答）
規則Qより、Qx→xであるので、CQx→xQxが成り立つ。
xがCのとき（以下「x = C のとき」と表現する）、CQC→CQCとなる。
∴それ自身をもたらすような記号列はCQC
＊＊＊＊＊
問２ それ自身の随伴をもたらすような記号列を見つけよ。
（解答）
求める記号列をxとして、
x→xQx ・・・・・①となるような記号列を探す。
随伴をもたらす記号列だから、xはCからはじまる記号列。そこで、x = Cx1とすると、①は、
Cx1→Cx1QCx1 ・・・・・①’と書ける。このとき、規則Cの条件より、
x1→Cx1 ・・・・・②が成り立たなければならない。②の式は規則Qにあてはまらないので、規則Cにあてはめるため、x1 = Cx2とすると、
Cx2→CCx2 ・・・・・②’と書ける。規則Cの条件を満たすようにするには、x2 = QCC とすればいい（②’の式での出力先の記号列にはQがないので、x2 = Qx3とすると、x3 = CC）。求める記号列はxであるため、
x = Cx1 = CCx2 = CCQCC
∴それ自身の随伴をもたらすような記号列はCCQCC
（考察）
・記号列CCQCCは、CCQCCの随伴CCQCCQCCQCCをもたらす。
・問１の解答途中で、CQx→xQxが成り立つことを確認した。CQx→xQxであるので、規則Cより、CCQx→xQxQxQxとなる。ここでx = CC としたのが問２の答えである。
・以下の規則は、本には載っていない（問題を解くためには使われている）
規則CQ CQx→xQx（xの随伴）
（任意の記号列xに対して、記号列CQxはxの随伴xQxをもたらす）
規則CCQ CCQx→xQxQxQx（xの随伴の随伴）
（任意の記号列xに対して、記号列CCQxはxの随伴の随伴をもたらす）
＊＊＊＊＊
問３ それ自身の随伴の随伴をもたらすような記号列を見つけよ。
（解答）
求める記号列をxとして、
x→xQxQxQx ・・・・・①となるような記号列を探す。
随伴をもたらす記号列だから、xはCからはじまる記号列。そこで、x = Cx1とすると、①は、
Cx1→Cx1QCx1QCx1QCx1 ・・・・・①’と書ける。このとき、規則Cの条件より、
x1→Cx1QCx1 ・・・・・②が成り立たなければならない。②の式は随伴をもたらすことを意味するので、x1はCからはじまる記号列。x1 = Cx2とすると、
Cx2→CCx2QCCx2 ・・・・・②’と書ける。このとき、規則Cの条件より、
x2→CCx2 ・・・・・③が成り立たなければならない。③の式は規則Qにあてはまらないので、規則Cにあてはめるため、x2 = Cx3とすると、
Cx3→CCCx3 ・・・・・③’規則Cの条件を満たすようにするには、x2 = QCCC とすればいい（③’の式での出力先の記号列にはQがないので、x3 = Qx4とすると、x4 = CCC）。求める記号列はxであるため、
x = Cx1 = CCx2 = CCCx3 = CCCQCCC
∴それ自身の随伴の随伴をもたらすような記号列はCCCQCCC
問４は次回にまわそう。