思いつきtweetをはっとく
多分これを元に細かいつじつま合わせをすればなんとかなると思うんですけど、そのガッツがないと言うかその前にやることがたくさんというか。それと、recursion theoryの一般的な結果が適用できてあっさり解ける可能性もあるのではというのもあります。
大学のパソコンの前に座ったら、真っ先にhttp://bit.ly/9hLIum で@kinaba さんが書いていた問題のことについて書こうと思っていたら、twhirlがまともに動いてくれなくてうっきー
posted at 23:35:50
方針としては、fとしてほとんどidentityなんだけれども、「complementが無限になるような正規言語全てに対して、intersectionが有限」なところでだけちょびっとfをいじる。
posted at 23:41:20
あ、実はMTT*の定義すらちゃんと把握していないけれども、recursively enumerableな全ての入力に対して終了する関数のクラス、というだけでいけるはず。
posted at 23:42:39
たぶんこれは成り立っていると思うのだけれども。
posted at 23:42:58
正規言語もr.e.だからr_nとか列挙する。ただし、有限個の文字列にしかマッチしないもの、有限個以外全ての文字列にマッチするものは除く。これらはfを全単射にすれば自明にいけるので。
posted at 23:46:17
LSIを保つのがちょっと厄介なのだけれども、これはr_nをとったときに、r_nとそのcomplementを考えて、densityが小さいものをとってきて、そっちを使うことでなんとかなりそう。
posted at 23:48:47
問題は、inductionの途中でfの定義域と値域のdensityが大きくなったときに起こるので、それを抑えてやればいい。ここはちょっと定かじゃない。
posted at 23:50:17
ただし、もちろんTuring Machineにはdensityを計算することができないので、代わりに「上手くいったら途中のr_nをcomplementに入れ替えてやり直し」とかやる。使う文字セットが有限ならこれでもちゃんと停止すると思うのだけれども、ちょっと不安。
posted at 23:52:17
@kinaba 今のところ、自分に対するメモ＋書いておくと@tri_iroさんとか@patho_logicさんのような自然数の組合せ論に私より強いひとが解いてくれるのではないかwktkなので、つながらないところは読み飛ばしてください…
posted at 23:53:59
@kinaba 今の方針でうまく行くならIRCPに入るはずです。ただし、fおよび逆像を求める関数の計算量はかなりやばいことになっていると思います。集合論者に計算量を期待するのは間違いですから。
posted at 23:55:33
@kinaba ごめんなさい、これはそのままでは成り立たないですね。えーと、正規言語の増加列(r_n)で"r_{n+1}-r_n"が無限個になるようなものを考えると、その差分から一個ずつ元を取ってくることによって全てのnに対してr_nとの交わりが有限なものがとれます。
posted at 00:01:24
@kinaba それで、この(r_n)を上手くとってやれば、全ての正規言語rに対して、(1)有限個にのみマッチ(2)有限個以外全てにマッチ(3)あるnに対して、rはr_nの部分集合(4)あるｎni
posted at 00:03:13
@kinaba えーと、このくらいのステージでの構想は、こっぴどく間違っていることも多いのであんまり気にしないでください…。このくらい書いておけば、@tri_iroさんあたりがあまりにひどい間違いは指摘してくれるだろうと思いまして。
posted at 00:05:50
吐き出してすっきりしたので昼ごはん食べて仕事する
posted at 00:15:04
