イヤンホホに意味のある量を

ㅤ

$n$-一般化イヤンホホ化操作

こちらの記事： 文字列のイヤンホホ化 (不見) による呼び方にはないイヤンホホ化操作をこの記事では考えます。

この記事では$2$-GIRのみを考えることにするため、以降GIRという場合は$2$-GIRを指すものとします。
これは任意の2文字以上の文字列$S$に対して無限に操作を繰り返せるので、停止しないです。
というかこれについては 数学デー において少し研究されていて、
任意の文字列$S$と$T$に対して、$S$にGIRを繰り返し行うことで$T$に変換できるかどうかの必要十分条件が判明しています。
1文字からなる文字列にはGIRは適用できないです。
かつ2文字以上の文字列にGIRを適用しても1文字にはできないので、$S$または$T$が1文字ならば$S=T$でない限り変換できないです。
$S,T$の両方が2文字以上ならば、$S$に含まれる文字全体の集合と$T$に含まれる文字全体の集合が等しい場合、かつその場合に限りGIRを繰り返すことで$S$から$T$へ変換できるっぽいです。

ㅤ

意味のある値

ここで、GIRという操作に対してあまり変化しない、意味のある値を考えていきたいです。
不変量、つまり常に一定の値をとるものはここではあまり意味がないです。なぜなら上記のように任意の文字列$S$と$T$について、$S$にGIRを繰り返すことで$T$に変換できるかどうかの必要十分条件がすでに分かっているからです。この条件から考えるに、$S$に含まれる文字全体の集合$\text{Set}(S)$がいい不変量になることが分かります。
しかしこの記事では主に"0"と"1"からなる文字列でかつ、"0"のみまたは"1"のみの文字列を除いたものを対象としているので、常に$\text{Set}(S)=\{\text{"0"},\text{"1"}\}$となります。よってこの不変量についてはあまり深追いしません。

これ以外の不変量はおそらくありません。なぜならば、$\text{Set}(S)$さえ変わらなければ任意の文字列に移れるからです。
よって、ここからは不変量のような常に変化しないものではなく、変化はするもののそこまで大きく動かない値を探していきます。

この先の議論では文字列と言えば"0"と"1"のみからなる文字列とします。

ㅤ

案1

"0","1"の2種類の文字のみからなる文字列$S$に対し、$S[i]$で$i$文字目の文字を表すものとします。

これは値が変わりやすすぎる
\begin{eqnarray} ・&&& f(00000010) &&= -5 \\ ・&&& f(000000011) &&= -14 \end{eqnarray}

ㅤ

案2

$S$を同じ文字の連続ごとに圧縮して以下のように表現します。(ランレングス圧縮というらしい)
\begin{eqnarray} S = X_1^{n_1}X_2^{n_2}X_3^{n_3}X_4^{n_4}\cdots X_k^{n_k} \end{eqnarray}
ただし$X_i$は"0"または"1"で、$k$は正の整数
$0^a$は"0"を$a$個続けるという意味。$1^4$は$1111$と同じ

例えば、
\begin{eqnarray} 0110000110001111 = 0^11^20^41^20^31^4 \end{eqnarray}
です
文字が何個連続しているか書いている感じです。

例えば、
\begin{eqnarray} 0110000110001111 = 0^11^20^41^20^31^4 \end{eqnarray}
なので、
\begin{eqnarray} \Phi_\text{diff}(0110000110001111) &=& \Phi_\text{diff}(0^11^20^41^20^31^4) \\&=& 1\cdot1+2\cdot(-1)+4\cdot1+2\cdot(-1)+3\cdot(1)+4\cdot(-1) \\&=& 1-2+4-2+3-4 \\&=&0 \end{eqnarray}

ここで気づいたのは、これは次と等価です。

こちらを定義とした方がよさそう

ㅤ

考えたかったこと

実は、元々上の$\Phi_\text{diff}$という関数は以下のように定義しようとしていたのです。

これを少し変形したのが上記の定義2でした。
(和を取る範囲を$k$から$k-1$へ変えると元々の定義しようとしていた値に一致する)

また、もう一つ意味のある値として文字列の長さが存在します。$|S|$と書くことにします。
しかし、$S$に現れる"0"の個数を$|S|_0$とし、"1"の個数を$|S|_1$とすると、$|S|=|S|_0+|S|_1$ですから、結局は$|S|_0$と$|S|_1$の和と差を持っているだけになります。

じゃぁ和と差を持つのではなく$|S|_0,|S|_1$をそれぞれ持っていれば良いのではと考えてしまいますが、実は和と差にしておく方がいいかもしれません。
なぜなら、$|S|_0,|S|_1$を個別に持っておくと、GIRをした時に片方の値は変わりません。しかし、和や差は毎回のGIRによって$+1$または$-1$されます。
まぁ後付けの理由ですが。
どちらがいいのかというのは使ってみて実感すればいいのです。

ㅤ

案3

他にはないでしょうか？さっきのランレングス圧縮というのは面白そうです。

この時、次のことが言えます。

ㅤ

最小ステップ数の評価

下界

この定理によって、$\Phi_0$や$\Phi_1$自体を見る意味はほぼなくなりました。(泣く)

ㅤ
ㅤ

この定理は次のように証明できます(離散空間のリプシッツ条件？というらしいがよく知らない)

ㅤ

ㅤ

あぁそれと、$\Phi$関連の言葉をまとめておきましょう

こうすると、さっきの定理5を拡張できます。

これはさっきの定理5の証明とほぼ同じようにできます。

この定理6より、次のことがすぐに言えます。

他にも下界に関していろいろとポテンシャルを考えてみましたが、なかなかいいものはありませんでした。

• $\Phi_\text{LCS}$:最長共通部分列 (LCS: Longest Common Subsequence
• $\Phi_\text{sqLCS}$:文字列を一度すべて圧縮（"00" $\to$ "0" などのスクイーズ）した状態でのLCSを計算
• $\Phi_\text{RLE\_add}$:$\Phi_\text{sqLCS}$ + ("0"を何文字圧縮したか) + ("1"を何文字圧縮したか)
• $\Phi_\text{RLE\_sub}$:$\Phi_\text{sqLCS}$ - ("0"を何文字圧縮したか) - ("1"を何文字圧縮したか)

$\Phi_\text{RLE\_sub}$の面白い特徴として、一度のGIRに対して必ず$+1$か$-1$されるという点があります。(理由は知らない)
ただほとんどが使い物にならない(それほど値が変わらない or リプシッツ定数が$3$など大きい)です。
それと、上記の使い物にならない物にかかわらず、どのポテンシャルも"01"$\to$"10"がだいたい$1$か$0$になってしまいました。まぁ仕方がないですね。

上界

下界は自明な下界として$1$があるのでさほど距離が遠くない文字列同士ならそれでも十分ですが、自明な上界は存在しないです。("01"$\to$"10"が自明でないから)
ということで上界を考えるほうが実は有意義だったりするかもしれません。考えてみましょう。

"01"$\to$"10"が可能であるという事実を使ってもいいですが、もうちょっと賢く行きたいですね。

よくある手法としては、今回は可逆な操作が可能なので基準形という形を設定し、文字列$S,T$から基準形までの距離を上から抑える方法があげられます。

問題は、基準形を何に取るかです。いい基準形を探さないといけません。
最初に考え付いたのは"00...011...1"もしくは"11...100...0"です。これは文字列にある"1"か"0"を全部左側に持っていけばいいので、必ず到達することが分かります。
じゃぁ基準形は"00...011...1"に

$1100100100110$なら、このようにできます。

GIRは、その変換方法から文字を左側に寄せるほうが簡単です。(赤を左に寄せようとする上図)
この図は イヤンホホパズル 可視化 という私のサイトで可視化することができます。

右側に寄せようとすると、思ったより手数がかかります。(青を右に寄せようとする上図)

では、計算してみましょうか、
書き換え規則は
\begin{eqnarray} 00 \to 000 \\ 11 \to 111 \\ 01 \to 100 \\ 10 \to 011 \\ 000 \to 00 \\ 111 \to 11 \\ 100 \to 01 \\ 011 \to 10 \end{eqnarray}
で全てですから、これをどこに適用するかだけ考えればいいです。
\begin{eqnarray} 000 \to 00 \\ 111 \to 11 \end{eqnarray}
これに関しては単純な収縮ですね。同じ文字が連続した文字列を最小で2文字まで小さくすることができます。
逆に、
\begin{eqnarray} 00 \to 000 \\ 11 \to 111 \end{eqnarray}
はぱっと見使い道が分かりません。しかし、こういう時に使えます。
\begin{eqnarray} &&1100 \\ &&11000 \\ &&110000 \\ &&10100 \\ &&1001 \\ &&011 \\ \end{eqnarray}
なるほど、"0"の個数を意図的に増やすことで$100\to01$をたくさん生み出しているんですね。
しかしまぁ、単純に"0"を左に動かそうと言う思いだけならどうなるでしょうか？
\begin{eqnarray} &&1100 \\ &&101 \\ &&0111 \\ \end{eqnarray}
となり、結果的にはあまり意味がないことが分かります。使わないでいいでしょう。
残りは
\begin{eqnarray} 01\to100\\ 10\to011\\ 100\to01\\ 011\to10 \end{eqnarray}
ですが、まぁ"0"と"1"のどちらを左側に寄せたいかで使うべき手が変わってきますよね。

• "0"を左に寄せたい場合: $10\to011$ or $100\to01$
• "1"を左に寄せたい場合: $01\to100$ or $011\to10$
  ということは、左に寄せたい文字が"0"だとしたら、一番右にある"0"について、
  $\,\,\,\cdots1\textbf{0}$となっていれば、$10\to011$を、
  $\cdots10\textbf{0}$となっていれば、$100\to01$を使えばいいということですね。
  この規則に従ってみたいところですが、如何せん複雑です。

とりあえずまぁ、これによって左側に"0"を、右側に"1"を寄せることができます。
一番右にある"0"について、かならずステップ(2)で左に1つずれることができるため、文字列$S$に対してこのアルゴリズムで基本形になるまでにかかる最長ステップ数は$|S|$です。

あとは、基本形同士の移り変わりにおけるステップ数の評価ですね。
そのために正規化されたときの
正規化アルゴリズムの(2)の i. では、文字列が伸びています。
しかし、"1"は三文字以上連続している時には二文字にまで縮まるので、
(1)や(3)を毎回適用していることから、(2)をする直前では"1"は最大でも二文字しか連続しません。
よって、最初から考えると i. は二回までしか連続して行えず、その後は必ず ii. または iii. が必ず行われます。

iii. を繰り返したのちには必ず ii. に到達します。
これが重要で、ii. の時の文字列は
(あ) $S0100S'$
または
(い) $S1100S'$の二通りに分けられます。($S'$は"1"が連続した文字列)
それと、(い) $S1100S'$は
(い)-a $S11100S'$
(い)-b $S01100S'$
の二通りが考えられますが、"1"は連続して3つ出てこないので、(い)-b $S01100S'$の場合しかありえません。

(あ) $S0100S'$の場合、
ii. によってこれは$S001S'$となり、
これは ii. または iii. に戻されます。

(い)-b $S01100S'$の場合
ii. によってこれは$S0101S'$となり、これは i. に移ります。
i. によって$S00111S'$となり、これは ii. または iii. に移ります。

ここで大事なのは
最初だけ i. は二度連続することがある。
その後、iii. が何度か行われ必ず ii. に移る。
ii. の後、ii. か iii. に移る　もしくは i. を一度だけ経由してから ii. に移る
ということです。
分かりにくいですよね？図にしてみました
\begin{xy} \xymatrix{ \text{i.} \ar[d] \\ \text{i.} \ar[r] & \text{iii.} \ar@(ur,ul)[] \ar[r] & \text{ii.} \ar[d] \ar[dl] \ar[dr] \\ & \text{iii.} & \text{ii.} & \text{i.} \ar[d] \ar[dl] \\ & & \text{ii.} & \text{iii.} }\end{xy}

図にはなりましたが、これでは同じ状態がいろんなところに登場しています。
もうちょっとまとめてみるとこうなります。
\begin{xy}\xymatrix{ & & \text{ii.} \ar@(ur,ul)[] \ar@/_/[dl] \ar@/_/[dr] \\ \text{i.} \ar[r] & \text{i.} \ar@/_/[ur] \ar@/_/[rr] & & \text{iii.} \ar@(dr,ur)[] \ar@/_/[ul] }\end{xy}

きれい。
...それが大事なのではなく、大事なのは i. に自己ループ(自分に帰ってきているループ)が無いということです。
ということは、i. によって文字列全体の長さが増えた後は、必ず ii. か iii. で全体の長さが縮みます。
i. は最大でも連続して2回しか起きないので、文字列全体の長さは最終的に3文字以上は増えないと分かります

この定理から考えると、文字列$S,T$を各々正規化した後には、$|S|+|T|-4$ステップがかかり、
$S$は$2\sim|S|+2$文字、$T$は$2\sim|T|+2$文字になっています。
また、$01\leftrightarrow 011$や$01\leftrightarrow001$や$01\leftrightarrow0011$や$001\leftrightarrow011$は以下のようにして可能です。
\begin{eqnarray} &[0]&01 \\ &[1]&100 \\ &[2]&1000 \\ &[3]&10000 \\ &[4]&0100 \\ &[5]&001 \\ \\ &[0]&01 \\ &[1]&100 \\ &[2]&0110 \\ &[3]&10010 \\ &[4]&100011 \\ &[5]&10011 \\ &[6]&0111 \\ &[7]&011 \\ \\ &[0]&01 \\ &[1]&100 \\ &[2]&1000 \\ &[3]&010 \\ &[4]&0011 \\ \\ &[0]&001 \\ &[1]&0100 \\ &[2]&10000 \\ &[3]&011000 \\ &[4]&01100 \\ &[5]&100100 \\ &[6]&10001 \\ &[7]&1001 \\ &[8]&011 \\ \end{eqnarray}

よって、正規化後の$S$と正規化後の$T$を双方$01,001,011,0011$のいずれかに移すのに最大$|S|+|T|+4$文字、そして最大でも8手でいずれからいずれへも変換可能ですから、
合計で$|S|+|T|-4+|S|+|T|+4+7 = 2(|S|+|T|)+8$手で移れるということになります。

上界の改善

ちょい多いと思います。まぁ$001\leftrightarrow110$が12手かかります。

これが最小手数なので、$2(|S|+|T|)+8 = 2(3+3)+8=20$ですから、ましな評価なのかもしれません。
本当にそうでしょうか。
$d(000000000000001,111111111111110)=36$です。
しかし$2(15+15)+8 = 68$です。おおい...
さすがに$|S|+|T|+(\text{定数})$ぐらいに抑えたいところです。

基本形を変えてみませんか？
新たな正規化アルゴリズムを考えてみました
今度は単純です

単純ですね。遷移も$\begin{xy}\xymatrix{\text{(1)}\ar@(ur,ul)[]}\end{xy} $ですから単純です。
しかし結果はどうなるのでしょうか？

まず、3文字以上同じ文字が連続することがありません。($000\to00,\;\;111\to11$による)
そして、同じ文字が2文字連続する、"00","11"があるのは一番左にある時だけです。
なぜなら、一番左に"00","11"がないなら、この左に逆の文字があるはずです。($\cdots100,\;\;\cdots011$のどちらか)
しかしこの状況はどちらも(1)が適用できてしまいます。($\cdots100\to\cdots01,\;\;\;\cdots011\to\cdots10$)
よって(1)が適用できない状態になれば、一番左以外には2文字連続することはありません。
ということは、実質的に以下のようなパターンに限られます。
\begin{eqnarray} &&001010\cdots01 \\ &&001010\cdots10 \\ &&110101\cdots10 \\ &&110101\cdots01 \\ &&0101\cdots01 \\ &&0101\cdots10 \\ &&1010\cdots10 \\ &&1010\cdots01 \\ \end{eqnarray}
まぁちょい複雑かもしれませんが...とりあえずいいでしょう。

今度はステップ数と正規化が終了したときの文字列の長さがどうなるか考えてみましょう。
といっても、今回すごく単純で、(1)は常に1文字短くするので、ステップ数と文字列の合計が常に一定の値になります。$S$を正規化するとして、ステップ0で文字列の長さが$|S|$なので、合計が$|S|$で一定であることが分かります。

あとは基本形同士の移り変わりです。
けど、いろいろ実験してみるといけそうな気がします。

この図を見るとなんか行けそうな気がしますね。

ㅤ

$\underbrace{0101\cdots0101}_{n\text{ times 01}}100$を$A(n)$型

$\underbrace{0101\cdots0101}_{n\text{ times 01}}1000$を$B(n)$型とします。
まぁ$L=01$とすれば
$L^n100$がA型
$L^n1000$がB型となります。($n$は非負整数)

$A(n),B(n),L^n$の行き来について考えてみましょう。
$A(n)$型の一番後ろの"00"の部分にGIRを適用して"000"にすると、$B(n)$型になります。
\begin{eqnarray} A(n) &=& L^n100 \\&\overset{\text{GIR}}{\longleftrightarrow}& L^n1000 \\&=& B(n) \end{eqnarray}
つまり、$\displaystyle{A(n)\overset{\text{GIR}}{\longleftarrow\!\longrightarrow} B(n)}$です。

次は、画像から$B(n)\to A(n+1)$の遷移を考えてみましょう
$B(n)$型の一番後ろにある"10"の部分を"011"にすると$A(n+1)$型になりそうです。
\begin{eqnarray} B(n) &=& L^n1000 \\&\overset{\text{GIR}}{\longleftrightarrow}& L^n01100 \\&=& L^nL100 \\&=& L^{n+1}100 \\&=& A(n+1) \end{eqnarray}
ということで、$\begin{xy}\xymatrix@C=40pt{A(n) \ar@{<->}[r]^{\text{GIR}} & B(n) \ar@{<->}[r]^-{\text{GIR}} & A(n+1)}\end{xy}$となります。

また、$L^{n+1}$と$A(n)$型が移り変われます。
\begin{eqnarray} L^{n+1} &=& L^nL \\&=& L^n01 \\&\overset{\text{GIR}}{\longleftrightarrow}& L^n100 \\&=& A(n) \end{eqnarray}
しかも、$L^{n+1}0$と$B(n)$型が移り変われます。
\begin{eqnarray} L^{n+1}0 &=& L^nL0 \\&=& L^n010 \\&\overset{\text{GIR}}{\longleftrightarrow}& L^n1000 \\&=& B(n) \end{eqnarray}

そうですね。図にしてみましょう。
\begin{xy}\xymatrix@C=40pt{ A(n) \ar@{<->}[r]^{\text{GIR}} & B(n) \ar@{<->}[r]^-{\text{GIR}} & A(n+1) \ar@{}[r]|{\Huge\cdots} & \\ L^{n+1} \ar@{<->}[u] & L^{n+1}0 \ar@{<->}[u] & L^{n+2} \ar@{<->}[u] }\end{xy}
これによって$A(n),B(n),L^{n+1},L^{n+1}0$同士の移り変わりに最低何ステップで行けるかが判明しました。

さて、
基本形同士の移り変わりを実際に計算していくステップに移りたいのですが、そもそも基本形はどんな形があったでしょうか？
\begin{eqnarray} &&001010\cdots01 &=& 0L^{n+1} \\ &&001010\cdots10 &=& 0L^{n+1}0\\ &&110101\cdots10 &=& 11L^n0\\ &&110101\cdots01 &=& 11L^{n+1}\\ &&0101\cdots01 &=& L^{n+1}\\ &&0101\cdots10 &=& L^{n+1}0\\ &&1010\cdots10 &=& 1L^n0\\ &&1010\cdots01 &=& 1L^{n+1}\\ \end{eqnarray}

それと、最初から短かったという可能性がありますから、
\begin{eqnarray} 10 \\ 01 \end{eqnarray}
という可能性もありますが、上記の$n$が非負整数であることから
\begin{eqnarray} 10 &=& 1L^00\\ 01 &=& L\\ \end{eqnarray}
という形で尽くされています。
上記の8種類は、どれも基本として$L^n$が真ん中にあって、その前後に付くものによってその個性を表していますね。
なので、一旦$A(n)$または$B(n)$にたどり着くまで何手かを数えればいい気がします。

$0L^{n+1}$の場合

$n\geqq2$の時はこうします。
\begin{eqnarray} 0L^{n+1} &=& 0L^2L^{n-2}L \\&=& 00101L^{n-2}01 \\&\overset{\text{GIR}}{\longleftrightarrow}& 000111L^{n-2}01 \\&\overset{\text{GIR}}{\longleftrightarrow}& 00111L^{n-2}01 \\&\overset{\text{GIR}}{\longleftrightarrow}& 0101L^{n-2}01 \\&\overset{\text{GIR}}{\longleftrightarrow}& 0101L^{n-2}100 \\&=& L^n100 \\&=& A(n) \end{eqnarray}
$n=0,1$の時は以下のようになります
\begin{eqnarray} 0L^1 &=& 001 \\&\overset{\text{GIR}}{\longleftrightarrow}& 0100 \\&\overset{\text{GIR}}{\longleftrightarrow}& 10000 \\&\overset{\text{GIR}}{\longleftrightarrow}& 1000 \\&\overset{\text{GIR}}{\longleftrightarrow}& 100 \\&=& A(0) \\\\ 0L^2 &=& 00101 \\&\overset{\text{GIR}}{\longleftrightarrow}& 000111 \\&\overset{\text{GIR}}{\longleftrightarrow}& 00111 \\&\overset{\text{GIR}}{\longleftrightarrow}& 0101 \\&\overset{\text{GIR}}{\longleftrightarrow}& 01100 \\&=& A(1) \end{eqnarray}

このことから、$d(0L^{n+1},A(n)) \leqq 4$と分かります。

$0L^{n+1}0$の場合

$0L^{n+1}0$については、$0L^{n+1}$の後ろに$0$がついただけですので、$A(n)$の後ろに$0$がついた$B(n)$に対して、
\begin{eqnarray} d(0L^{n+1}0,B(n)) \leqq 4 \end{eqnarray}
が言えます。

$11L^{n}0$の場合

$n\geqq1$については、以下の遷移を使います。
\begin{eqnarray} &[0]&1101 \\ &[1]&11100 \\ &[2]&1100 \\ &[3]&10110 \\ &[4]&011110 \\ &[5]&01110 \\ &[6]&0110 \\ &[7]&100 \\ &[8]&01 \end{eqnarray}
つまり、$d(1101,01) \leqq 8$です。
この文字列の末尾に$L^{n-1}0$を付ければ、
$d(1101L^{n-1}0,01L^{n-1}0) \leqq 8$
\begin{eqnarray} d(1101L^{n-1}0,01L^{n-1}0) \leqq 8 \\ d(11L^{n}0,L^{n}0) \leqq 8 \\ \end{eqnarray}
が分かり、$d(B(n),L^{n+1}0) = 1$より
\begin{eqnarray} d(11L^n0,B(n-1)) \leqq 9 \end{eqnarray}
です。
$n=0$については、
\begin{eqnarray} &[0]&110\\ &[1]&1011\\ &[2]&11001\\ &[3]&101101\\ &[4]&0111101\\ &[5]&011101\\ &[6]&01101\\ &[7]&011100 \\ &[8]&01100 \\ &[9]&1000 \\ \end{eqnarray}
という遷移で、9手以下で$B(0)$に移ることができます。

$11L^{n+1}$の場合

先ほどの$d(1101,01) \leqq 8$を使えば、
$d(1101L^n,01L^n) \leqq 8$です。
そして$d(A(n),L^{n+1}) = 1$ですから、
$d(11L^{n+1},A(n)) \leqq 9$と分かります

$1L^n0$の場合

$n\geqq2$の時は、以下の遷移を使います
\begin{eqnarray} &[0]&10101\\ &[1]&101100\\ &[2]&0111100\\ &[3]&011100\\ &[4]&01100\\ &[5]&0101\\ \end{eqnarray}
$d(10101,0101) \leqq 5$であるから、
$d(10101L^{n-2}0,0101L^{n-2}0)\leqq 5$
つまり、
$d(1L^{n}0,L^n0) \leqq 5$です。ここから
$d(1L^n0,B(n-1)) \leqq 6$と分かります。
$n=0,1$の場合は、以下のようにします。
\begin{eqnarray} &[0]&10\\ &[1]&011\\ &[2]&1001\\ &[3]&01101\\ &[4]&011100\\ &[5]&01100\\ &[6]&1000\\ \\ &[0]&1010 \\ &[1]&01110\\ &[2]&0110\\ &[3]&100\\ &[4]&1000 \end{eqnarray}

$1L^{n+1}$の場合

これは、$1L^n0$の場合の末尾に$1$を付ければいいです。
すると、$d(1L^n01,B(n-1)0) \leqq 6$と分かるので、
$d(1L^{n+1},B(n-1)) \leqq 7$と分かります。
($B(n)0 = L^n10000 \overset{\text{GIR}}{\longleftrightarrow} L^n1000 = B(n)$より、一手で行ける)

基本形全体の集合を$X(n)$とします。
\begin{eqnarray} X(n) = \{ 0L^{n+1} ,\;\; 0L^{n+1}0,\;\; 11L^n0,\;\; 11L^{n+1},\;\; L^{n+1},\;\; L^{n+1}0,\;\; 1L^n0,\;\; 1L^{n+1} \} \end{eqnarray}
$X(n)$の各元の長さは、
\begin{eqnarray} |0L^{n+1} |&=&2n+3,\;\; |0L^{n+1}0|&=&2n+4,\\ |11L^n0|&=&2n+3,\;\; |11L^{n+1}|&=&2n+4,\\ |L^{n+1}|&=&2n+2,\;\; |L^{n+1}0|&=&2n+3,\\ |1L^n0|&=&2n+2,\;\; |1L^{n+1}|&=&2n+4 \end{eqnarray}
さらに$|A(n)|=2n+3,|B(n)|=2n+4$ということを頭に入れておきましょう。

前の結果から、任意の元$x_n\in X(n)$に対して、$d(x_n,A(n))\leqq 10$と分かります。
さらに、$\big||x_n|-|A(n)|\big| \leqq 1$です。

任意の文字列$S,T$に対してその正規化した形を$S',T'$とすると、
\begin{eqnarray} d(S,S') \leqq|S|-|S'| \\ d(T,T') \leqq|T|-|T'| \\ \end{eqnarray}
そして、$S'$から一番近い$A(n)$型の文字列があるので、その$n$を$n_S$とし、同様に$T$の方も$n_T$と定義します。

先ほどの結論より
$\big||S'|-|A(n_S)|\big| \leqq 1$
$\big||T'|-|A(n_T)|\big| \leqq 1$
ですから、
$\vert{}A(n_S)\vert{} \ge \vert{}S'\vert{} - 1$
$\vert{}A(n_T)\vert{} - \vert{}T'\vert{} \leqq 1$
が分かります。

さらに、基本形から$A$型への往復コストはそれぞれ10手以下です。
$d(S', A(n_S)) \leqq 10$
$d(A(n_T), T') \leqq 10$

また、$A(n_S),A(n_T)$間の最短手数はその長さの差に一致します。
$$d(A(n_S), A(n_T)) = 2(n_T - n_S) = \vert{}A(n_T)\vert{} - \vert{}A(n_S)\vert{}$$

ここまでの不等式を使い、$d(S,T)$を評価していきます
\begin{aligned} d(S, T) &\leqq d(S, S') + d(S', A(n_S)) + d(A(n_S), A(n_T)) + d(A(n_T), T') + d(T', T) \\ &\leqq (\vert{}S\vert{} - \vert{}S'\vert{}) + 10 + \big( \vert{}A(n_T)\vert{} - \vert{}A(n_S)\vert{} \big) + 10 + (\vert{}T\vert{} - \vert{}T'\vert{}) \\ &= \vert{}S\vert{} + \vert{}T\vert{} + 20 + \big( \vert{}A(n_T)\vert{} - \vert{}T'\vert{} \big) - \big( \vert{}A(n_S)\vert{} + \vert{}S'\vert{} \big) \\&\leqq \vert{}S\vert{} + \vert{}T\vert{} + 20 + 1 - \big( (\vert{}S'\vert{} - 1) + \vert{}S'\vert{} \big) \\ &= \vert{}S\vert{} + \vert{}T\vert{} - 2\vert{}S'\vert{} + 22 \end{aligned}

そして、$|S'|\geqq2$です。

以上により、以下の定理が導かれます。

終わりに

多分もうちょっと$d(S,T)$は絞れるので、明日にでも記事を更新したいと思います
(特に最後の方急に雑くなった)