Xirdim /ひるでぃむ/ @低浮上？
@xirdim
すでに指摘されてしまいましたが… 一応自分で証明考えたやつ（車輪の再発明み）を書き留めとく。 (i) |ℂ|=1 のとき ℂ の唯一の元を 𝑐 として 𝑓: ℕ→𝕊, 𝑓(𝑥) = 𝑐×(𝑥-1) とすると 𝑓 は全単射. ∴ |𝕊|=|ℕ|=ℵ₀ twitter.com/Ziphil/status/…
2022-07-01 00:05:25
Ziphil “Ziphineko” Shaleiras 🐈
@Ziphil
この辺、文字列全体が可算集合なので、その部分集合は無限なら全部可算なので等濃度になっちゃう。
2022-06-30 20:52:50
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
(ii) |ℂ|=2 のとき twitter.com/xirdim/status/… より, ℂ = {"0", "1"} のみを考えればよい. 𝑓: 𝕊→ℕ² を考え, 𝑓(𝑠) を次のように定める: 𝑚 = (𝑠 の先頭部分に続く "0" の数) (≥0) 𝑛 = (𝑠 を2進法表記の整数とみなしたときに 𝑠 が表す数. 𝑠∈/0*/ なら 0 とする) 𝑓(𝑠) = (𝑚, 𝑛)
2022-07-01 00:16:34
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
まあこれ当たり前なんだけども一応ね。 |ℂ₁|=|ℂ₂| より、全単射 𝑓: ℂ₁→ℂ₂ が作れる。 ここで、𝑔: 𝕊₁→𝕊₂ を考え、𝑔(𝑠) を「𝑠 に含まれる文字 𝑐 を 𝑓(𝑐) に置き換えた文字列」とすると、𝑔 は全単射 ∴ |𝕊₁|=|𝕊₂| twitter.com/xirdim/status/…
2022-06-29 23:41:35
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
(ii) の別案. 回りくどいのでボツにしたけど, わりと気に入ってるので書き留める. (以下, 厳密な書き方はしてない) 𝑓: 𝕊→ℕ として 𝑓(𝑠) を次のように定める: 𝑠 を先頭から見ていって, ・0 が続く数 (≥0) ・1 が続く数 (以下, ≥1) ・0 が続く数 ・1 が続く数 を考えて↓
2022-07-01 00:27:32
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
↓上から 𝑎₁,𝑎₂,𝑎₃,... とする. また, 素数を小さいものから順に 𝑝₁,𝑝₂,𝑝₃,... とする. f(s) = 𝑝₁^𝑎₁・𝑝₂^𝑎₂・𝑝₃^𝑎₃・… すると 𝑓 は単射. また, ℕ から 𝕊 へは自明な単射が存在. ∴|𝕊|=|ℕ|=ℵ₀
2022-07-01 00:27:34
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
(iii) |ℂ|≥3 のとき, ℂ₂={"0", "1"} とし, これを文字セットとする文字列全体集合を 𝕊₂ とする. ℂ⊃ℂ₂ であるような ℂ のみを考えればよい. このとき恒等写像 𝕊₂→𝕊 は単射. また, |ℂ₂|=2, ℂ:有限集合 より, ∃𝑛∈ℕ, |ℂ|≤|ℂ₂ⁿ| ↓
2022-07-01 00:49:08
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
↓ ここで, 𝑡∈ℂ₂ⁿ, 𝑡=(𝑎₁, 𝑎₂,..., 𝑎ₙ) に対して 𝐒(𝑡) = 𝑎₁+𝑎₂+…+ 𝑎ₙ ←要するに組の中の文字を順に繋げてる とすると, 単射 𝑔: ℂ→𝐒(ℂ₂ⁿ) が作れる. ↓
2022-07-01 00:49:10
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
↓ ℎ: 𝕊→𝕊₂ について, ℎ(𝑠) を「𝑠 に含まれる文字 𝑐∈ℂ を 𝑔(𝑐) に置き換えた文字列」とすると, 𝐒(ℂ₂ⁿ) の元たる文字列は全て長さが等しいことから, ℎ は単射である. (ii) より |𝕊₂|₌|ℕ| であるから, 以上より, |𝕊|₌|𝕊₂|₌|ℕ|=ℵ₀
2022-07-01 00:49:10
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
(i)(ii)(iii) より、 ∀ℂ:有限文字セット, |ℂ|>0 について、それによって得られる文字列全体集合 𝕊 は可算無限集合 //
2022-07-01 00:50:07
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
目標。 𝕊 の部分集合 A について語形変化 f: A → 𝕊 を定義したときに、 ・値域 B を求める。 ・写像 F: 2ᴬ → 2ᴮ, A₁ ↦ {f(σ) | σ∈A₁} を定める。 ・写像 F': 2ᴮ → 2ᴬ, B₁ ↦ {σ | f(σ)∈B₁} を定める。 ※イメージは逆写像だけど、逆写像とは限らないから F⁻¹ とは書かなかった
2022-08-10 16:20:06
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
その前に、正規表現の同値性を確かめる方法を考える必要がありそう /.*./ と /.*.*./ と /.+.?/ とか、/(a?b?){3}/ と /a?(b?a?){2}b?/ とか。けっこう難しい
2022-08-10 17:13:43
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
有限回の繰り返し・選択肢は全て展開し「|」だけで分岐しよう /(li){2}/ → /lili/ /.?/ → /|./ → /|a|i|u|e|o|k|s|t|n|p|m|j|l|w/（文字全体集合がトキポナ仕様の場合） /[sp]?ona/ → /(s|p)?ona/ → /(|s|p)ona/ → /ona|sona|pona/ といったように。有限集合だったらこれで要素の列挙になる
2022-08-10 17:36:38
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
2つめは、「.」の展開を先にやって /.?/ → /(a|i|u|e|o|k|s|t|n|p|m|j|l|w)?/ → /|a|i|u|e|o|k|s|t|n|p|m|j|l|w/ としたほうが良いな。 内側から先に計算する感じで
2022-08-10 17:39:04
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
無限集合の場合はもっと考えないといけない。 無限集合が生じるのは「?」や「+」や「{\𝓃,}」(\𝓃 は非負整数) が使われるとき。つまり上限のない繰り返し
2022-08-10 17:42:22
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
というか、こうは言うものの本当に無秩序な集合（{a, kon, soweli, kijetesantakalu, …}(何の規則性もなく無限に続く) のように）は人間の使う言語ではありえないな（記憶のしようがないから）。文法としての記述も不能 加算集合で考えれば十分なのでは？ twitter.com/xirdim/status/…
2022-08-10 17:53:34
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
正規表現において「*」などが生じうる無限は、可算無限だから、 そういった記法が有限個使われた正規表現は、高々、可算無限集合の有限個の直積と同濃度の集合にしかならないはず。つまり可算無限
2022-08-10 18:05:04
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
やること間違えた() 正規表現で表される集合（文字列全体集合の部分集合）の濃度についてじゃなくて、 正規表現で表される集合の集合（文字列集合全体集合の部分集合）の濃度について議論したいんだった 文字列全体集合が可算集合なんだから、正規表現で表される集合も高々可算集合に決まってる
2022-08-10 18:08:37
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
|(正規表現で表される集合の全体集合)| ≤ |(正規表現の中身の全体集合)| ≤ |𝕊| = ℵ₀ 正規表現で表される集合の全体集合 は無限集合。 ∴これは可算集合。Q.E.D. 正規表現の中身（/.*/ だったら「.*」）も文字列なんだから、文字列全体集合の濃度以下でしょ、という意味
2022-08-10 18:17:12
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
というか、（人間による使用を想定した）任意の言語で、その語形変化の規則は人間の言葉で説明できるはず。 人間の言葉は可算集合なんだから（線条性のある文字体系で表せることから明らか）、語形変化規則の全体集合も可算集合のはず
2022-08-10 18:24:32
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
任意の可算集合 A について、A から A への写像を元とする任意の可算集合 B を考える。A から A への写像を適当に有限個用意すれば、その適当な合成で、B の任意の元と等しい写像を作れるか？
2022-08-11 17:45:11
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
というわけで、できるかどうか分からないまま見切り発車になってしまうけど、この写像 f をより小さい単位に分解していくことを考える twitter.com/xirdim/status/…
2022-08-19 17:28:32
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
とりあえず語尾を付け替えるのは必須と。語頭や語中も必要だな。 あと「何文字目に何」とかでの条件分岐も必要だけど、その辺は正規表現にヒットするかどうかでカバーできる。
2022-08-19 17:35:44
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
オエル語のコピュラみたいに大量の接辞が規則的につくようなのにも対応することを考えると、活用形名も同時に算出することを見据える必要がある
2022-08-19 18:06:47
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
ところで、なんか核心に踏み込めない感じだった理由がわかった気がする；語形変化にはどういうパターンがあるのかという類型を全然知らない（致命的() （自然言語含め）そこら辺を調べるとするか
2022-08-19 18:08:40
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
ググったけどこの手の網羅的な情報が出てこない。というわけで見切り発車するしかないかなになった twitter.com/xirdim/status/…
2022-08-21 14:34:53
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
想定しておくべきことを纏めると、 ・辞書形に加えて、さらに幾つかのパラメータをとれることが必要 ・変化形名を同時に生成できることが必要 ・定数（e.g. 母音リスト：「後ろからn番目の母音を〜」とかに対応するため）を定義できることが必要
2022-08-21 14:36:26
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
あと、写像の定義が循環すると無限ループの判定に困るなぁ、となっていたが、 チューリング「無限ループの検出は不可能」 ∴あきらめる （そもそも写像の定義どうしの循環参照を許さないことにする；不自由がでてきたらまた考える）
2022-08-21 14:39:23
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
あれ、〈ある語形に対して変化形の綴りが複数ある〉みたいな変化パターンを考えると、もはや写像にすらならない やはり集合から集合への写像として定義すべきなのか
2022-08-21 15:25:06
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
少しアプローチを変えてみる： /(.+)(.)/ ↦ /$2$1/ こういうやり方は結構汎用性が高い。 （ちなみに上の例はフュトルの「転回」のひとつ）
2022-08-21 15:34:36
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
ただこれだと語幹の母音を規則的に変換するとか（変換規則の一部をこの記法の外部に委ねる）ができない。 よって、 /(.+)(a|o|u)(.)/ ↦ /$1\f($2)$3i/ ただし写像 \f で a↦ä, o↦ö, u↦ü みたいな機能をする記法が必要になるな
2022-08-21 15:43:15
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
いつの間にか「"プログラミングの知識がなくても"変化パターンを実装できる土台を作りたい」という最初の目標から離れてきたんだけど…()
2022-08-21 16:24:08
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
𝑇ℎ𝑒 𝑚𝑜𝑟𝑒 𝑐𝑜𝑚𝑝𝑙𝑖𝑐𝑎𝑡𝑒𝑑 𝑏𝑒𝑐𝑜𝑚𝑒 𝑡ℎ𝑒 𝑜𝑏𝑗𝑒𝑐𝑡𝑠 𝑦𝑜𝑢 𝑡𝑟𝑦 𝑡𝑜 𝑐𝑜𝑣𝑒𝑟, 𝑡ℎ𝑒 𝑚𝑜𝑟𝑒 𝑐𝑜𝑚𝑝𝑙𝑖𝑐𝑎𝑡𝑒𝑑 𝑦𝑜𝑢𝑟 𝑠𝑡𝑟𝑎𝑡𝑒𝑔𝑦. 〜網羅せんとする対象が複雑になればなるほど，その作戦もまた複雑になるのだよ． #ない名言
2022-08-21 16:26:42
Xirdim /ひるでぃむ/ @低浮上？
@xirdim
複雑でもいいから汎用的なやつを作り、そのあと、初心者でも扱いやすいようにしたサブセットを作るという方法で解決しよう twitter.com/xirdim/status/…
2022-08-21 16:42:55