「Tree3の停止性証明 第12章 String≦ （2021/05/08)」

Tree3の停止性証明 第12章 String≦

---

今回は新しい概念のstring≦を導入します。

とある型Tよりも、(int i = 5)
Tを使った配列 Array＜T＞ (int[ ] x = {1,2,3,4,5,6,7,8,9})の方が
遥かに複雑な情報を持てます。
これは1次元 vs 2次元の構造に近いです。


Higmanの定理は、
　　「Tで作るシークエンスが停止するなら、Array＜T＞で作るシークエンスも停止する」
と言う事を示している、めっちゃ強力な定理です。

---

ここら辺はコンパクト性定理とかにちょっと似てますよね。
　1次元コンパクト　→　2次元コンパクトが成立する
　1次元wqo　→　2次元wqoが成立する。
このHigman定理もそれに近い事をしています


言うて。
数学において1次元で成立する性質は
2次元でも、n次元でも
成立する傾向が高いです。

これはまあ。
1次元の線分濃度と2次元の線分濃度は同一であり(どちらもサイズω1)。
両者には1:1で滑らかにマッピングする方法が存在するので、
割と当然なのかもしれないですが。

---

もちろん例外はいくらでもあります。
例外1：
　　1次元ランダムウォーク →　元の場所に戻ってくる
　　2次元ランダムウォーク →　元の場所に戻ってくる
　　3,4,5,....次元ランダムウォーク →　元の場所に戻ってこれない

例外2：
　　グラハム数問題。
　　1,2,3,......次元立方体はモノクロ塗り分けが可能である。
　　[グラハム数]次元立方体はモノクロ塗り分けが不可能である。
　　
など。　　
あくまで「成立する傾向がある」ってだけで、現実はそこまでシンプルではありません。^^;　　

---