https://twitter.com/kinaba のログ (twilog の方が便利です。)
| http://d.hatena.ne.jp/ku-ma-me/20100407/p2 チューリング完全ではあると思うけど違うかなあ。two counter machine をダイレクトにエンコードできると思う。 | |
| @mametter 参照実装だと桂馬を使わない限りはBignumだし、specにもその実装を妨げる記述もないので、問題ないかなあと | |
| @mametter 足し算とジャンプがあれば割り算を作るには十分じゃなかろか。modがあるのでもっと楽。{x-=x%y; a=b=0; while(b!=x){a+=1; b+=y;} x=a;} で x/=y。 | |
| @kururu_goedel 「長さが同じ受理文字列の数」が「有界」になる方に Slender Language という名前がついていますが、オートマトンの状態数と絡めた議論があったかどうかちょっと記憶にないです。すみません。キーワードだけ投下 | |
| http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V1G-45H35FF-H&_user=10&_coverDate=08%2F16%2F1993&_rdoc=1&_fmt=high&_orig=search&_sort=d&_docanchor=&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=a8fb3c8720387c848e89d2ab30da982c の定理5.2 が"slenderness of an unambiguous CFL is decidable"だそうです （※unambiguous CFLは正規言語を真に含みます）。 | |
| Handbook of Formal Languages は全巻手元に置いておく必要があるなあ… | |
| 本屋に寄ってる。タビと道づれの6巻とSAOの4巻と3月のライオン4巻が同時に来たような大騒ぎです！！やほーい！ | |
| 手元の環境だとGoogle Waveが正視に耐えない重さなので久しく見ていなかったC++のアレの話が思いっきり進んでいる。ひー。今週末に頑張って仕上げよう。 |