機械に、ある記号列 x を入力すると、ある記号列 y をもたらす。この機械には3つの規則（規則Q、規則C、規則R）がある。
規則Q Qx → xまずは問５～問８まで解いていこう。
（任意の記号列 x に対して、記号列 Qx は x をもたらす）
規則C x → y ならば、Cx → yQy
（x が y をもたらすならば、Cx は y の随伴 yQy をもたらす）
規則R x → y ならば、Rx → yy
（x が y をもたらすならば、Rx は yy、すなわち y の反復をもたらす）
＊＊＊＊＊
問５ それ自身の反復をもたらすような記号列を見つけよ。
（解答）
求める記号列を x とすると、x それ自身の反復をもたらすような記号列であるので、
x → xx ・・・・・①となるような記号列 x を探すことになる。反復をもたらしているため、x = Rx1 とすると、①は、
Rx1 → Rx1Rx1 ・・・・・①’と書ける。このとき、規則Rの条件より、
x1 → Rx1 ・・・・・②でなければならない。
問４で、CQyC → yCQyC を導いた。ここで y = R とすると、CQRC → RCQRC となり、②の x1 を x1 = CQRC としたものに一致する。
∴それ自身の反復をもたらすような記号列は RCQRC
＊＊＊＊＊
問６ それ自身の随伴の反復をもたらすような記号列を見つけよ。
（解答）
求める記号列を x とすると、x それ自身の随伴の反復をもたらすような記号列であるので、
x → xQxxQx ・・・・・①となるような記号列 x を探すことになる。反復のかたちであるので、x = Rx1 とすると、①は、
Rx1 → Rx1QRx1Rx1QRx1 ・・・・・①’と書ける。このとき、規則Rの条件より、
x1 → Rx1QRx1 ・・・・・②でなければならない。随伴のかたちであるので、x1 = Cx2 とすると、②は、
Cx2 → RCx2QRCx2 ・・・・・②’と書ける。このとき、規則Cの条件より、
x2 → RCx2 ・・・・・③でなければならない。
CQyC → yCQyC で y = RC とすると、CQRCC → RCCQRCC となり、③の x2 を x2 = CQRCCとしたものに一致する。
求める記号列は x であるため、
x = Rx1 = RCx2 = RCCQRCC
∴それ自身の随伴の反復をもたらすような記号列は RCCQRCC
＊＊＊＊＊
問７ それ自身の反復の随伴をもたらすような記号列を見つけよ。
（解答）
求める記号列を x とすると、x それ自身の反復の随伴をもたらすような記号列であるので、
x → xxQxx ・・・・・①となるような記号列 x を探すことになる。随伴のかたちであるので、x = Cx1 とすると、①は、
Cx1 → Cx1Cx1QCx1Cx1 ・・・・・①’と書ける。このとき、規則Cの条件より、
x1 → Cx1Cx1 ・・・・・②でなければならない。反復のかたちであるので、x1 = Rx2 とすると、②は、
Rx2 → CRx2CRx2 ・・・・・②’と書ける。このとき、規則Rの条件より、
x2 → CRx2 ・・・・・③でなければならない。
CQyC → yCQyC で y = CR とすると、CQCRC → CRCQCRC となり、③の x2 を x2 = CQCRCとしたものに一致する。
求める記号列は x であるため、
x = Cx1 = CRx2 = CRCQCRC
∴それ自身の随伴の反復をもたらすような記号列は CRCQCRC
＊＊＊＊＊
問８ それ自身の反復の反復、すなわち xxxx をもたらすような x を見つけよ。
（解答）
求める記号列を x とすると、
x → xxxx ・・・・・①となるような記号列 x を探すことになる。反復のかたちであるので、x = Rx1 とすると、①は、
Rx1 → Rx1Rx1Rx1Rx1 ・・・・・①’と書ける。このとき、規則Rの条件より、
x1 → Rx1Rx1 ・・・・・②でなければならない。反復のかたちであるので、x1 = Rx2 とすると、②は、
Rx2 → RRx2RRx2 ・・・・・②’と書ける。このとき、規則Rの条件より、
x2 → RRx2 ・・・・・③でなければならない。
CQyC → yCQyC で y = RR とすると、CQRRC → RRCQRRC となり、③の x2 を x2 = CQRRCとしたものに一致する。
求める記号列は x であるため、
x = Rx1 = RRx2 = RRCQRRC
∴それ自身の随伴の反復をもたらすような記号列は RRCQRRC
＊＊＊＊＊
（つづく）
0 件のコメント:
コメントを投稿