https://twitter.com/kinaba のログ (twilog の方が便利です。)
| ディレクトリ操作に関するドキュメントを英語で書こうとしていて、「直接的に (directly)」って書きたいところをことごとく手が勝手に directory と書いてしまう作業を繰り返している。 | |
| @hyuki トリィとトリをtlyとtoryに正しく振り分けるのはなかなか難しそうです…(^^; | |
| そういえばXMDFの電子書籍ビューワのツールバーによく似た色の rgb(255,133,161) さんが http://gyazo.com/1ddc78c85e0375f7e48833d25a99cf07 どう設定しても開き直すたびに現れるので、いつも少しびっくりする | |
| 関数 f に対して {g | ∃c. ∃x0. ∀x>x0. g(x) < c f(x)} という集合はよく扱うわけですけど {g | ∃c. ∃x0. ∀x>x0. g(x) < f(x+c)} という集合を似たような用途で考える意味はあるだろうか的なことを考えていた。 | |
| 何を考えていたかというと https://t.co/UEF7wDoz を見て、「無駄なことをしていいなら任意の計算可能な関数fについてΘ(f(n))時間かけたあとにソート結果を返す関数が自明に作れるのだから面白くないじゃないですかー」と考えた結果がその記事だったのですけど | |
| よく考えたらその制限なし部門も面白い気がしてきた、というのはつまり、「今から１分でできるだけ増加が速い関数を実装せよ」って言われてとっさにackermann(x,x)より本質的に速いのが出せる人って少ないと思うんですよ。で、1分で難しいなら当然時間制限なしでも難しいので面白いはず | |
| というところまで考えたところで、その"本質的に速い"を厳密に定義して下さいというセルフツッコミが入って、big O記法的な意味だとackermann(x+1,x+1) とかが既に速くなってしまうのでそういうのを許さないようなオーダーっぽいものの定義を考えていた | |
| @stac_task そうそうまさにそれです。それとかackをack段重ねるくらいのものはまだまだ甘い、と言えるような比較基準って何かあったっけ、ということを考えていました。 | |
| と考え始めた0.4秒後くらいに https://t.co/PSybSP45 このツイートを書き出したので結論までまだ考えたり記憶を探り返したりしてない | |
| @syamino @Taroupho そのラインはありな気がしてきました。有限回の原始帰納法で書けないからアッカーマンは有限のkのk重帰納法のより速いみたいな雰囲気なので、極限順序数を超えるたびに真に速くなったとするとかでしょうか（あまりこの辺よくわかってない） | |
| しかし余りおおざっぱに区切りすぎて計算可能な関数全部区別できなくなったら困る | |
| @Taroupho あいやー確かに |