最終授業。前回に引き続きチューリングマシンについて。チューリングマシンの特徴はストリームがあいてではなく、テープが相手になるということ。つまり、双方向に移動ができるということにある。
よって、遷移関数には移動方向が含まれる。スタックはテープの奥の方に実現することで可能なので、PDAで表現可能な言語はチューリングマシン(TM)でも可能である。
遷移関数は定義されない場合があり、この場合はTMは停止する。また、双方向に移動するという性格だろうか（おそらく）、停止しないということがあり得る。
L=L(M),M=TMの形で表される言語Ｌは帰納的加算(recursive enumerable)という。また、TMが停止することで表すことのできる言語を帰納的（または計算可能）という。ここでチョムスキーは各機械が処理できるクラスは以下のような関係にあると証明した。
finite automaton≦pushdown automaton≦recursive≦recursive enumerable
先生は帰納的と帰納的加算の違いは、大きいといった。なぜなら、在籍して間もない頃、大雪の日にバスが来なくて、それを待つべきか待たないべきかで迷ったからだという。つまり、帰納的なのか帰納的加算なのかがわからないと、終わるかどうかがわからない。これと同様に、何時間経ってもバスが来ないとき、帰納的加算なのか、帰納的なのかという判断はとても難しいのだと思い知らされたと。私も前の大学ではバス通学だったので、その気持ちはよーくわかった。
で、帰納的加算と帰納的がわからなくなったら、これをおもいだしてくださいということで、講義はおわった。
