やったこと

研究

Immerman-Szelepcsényiの定理について考えていた。
NSPACE = co-NSPACEというやつ。
使えるテープ長に制限があるチューリングマシンは否定に閉じている、ということ。
直感的には、入力文字列の長さに対して様相の総数が有限なので、全通りシミュレートすることで否定が計算できる、ということになる。
この辺りをまとめた記事を書きたい。
時間はあるだろうか。