白と黒のとびら

白と黒のとびら: オートマトンと形式言語をめぐる冒険

魔法使いに弟子入りした少年ガレット．彼は魔法使いになるための勉強をしていくなかで，奇妙な「遺跡」や「言語」に出会います．最後の謎を解いたとき，主人公におとずれたのは……

http://www.utp.or.jp/bd/978-4-13-063357-4.html

こんなふうにオートマトンと形式言語に関連するテーマで１つのストーリーになっている。ある程度わかってる人たちは読んでると先が読める部分があると思うけど、それはそれで面白くて、主人公のガレットよ頑張れという気持ちになった。もちろん、オートマトンなんて単語も聞いたことない人でも読めて、最後にはチューリングマシンとはなんだとか、チューリングマシンで解けない計算問題とはどんなものかというところまで分かる。

ガレットに対する師からの言葉には身につまされる部分が多くて、辛い感じになるところもあった……身が引きしまる。

対角線言語

解説にあった対角線言語という単語を知らなかった。対角線言語はチューリングマシンに入力する文字列のうち、記述するチューリングマシンによって受理される文字列を除いた集合だと解説には書いてある。すなわち、受理されない文字列の集合。

受理されない文字列には「そもそもチューリングマシンを記述しない文字列」と「記述するチューリングマシンで受理されない文字列」がある。対角線言語を受理できるチューリングマシンがあるとその文字列は受理可能だという矛盾が生じるので、対角線言語を定義できるチューリングマシンは存在しない。