2006年 11月 24日
北朝鮮問題の手詰まり…千日手…数学的モズ歌…ＲＳＡ暗号共同発明者ロナルド・リベスト氏からのメール
|
今年９月から１０月までほぼ丸一ヶ月間当ブログが（完全に）沈黙していた時期がある．この空白期は９月８日付の「カッシーニ：バーチャルキャラ」説というトンデモ記事を発信してしまった後遺症（投稿自粛）とも言えるが，「北朝鮮の核実験実施は東アジアの平和を恒久的に破壊する戦争犯罪行為であり断じて許されない」と題する１０月６日付アッピールまでの期間，私は密かに『北朝鮮核問題解決策の手詰まり』を「数学的に定式化する」ことを試みていた．
←ご協力お願いします！
将棋では指し手が堂々巡りするような盤面を「千日手」と称して引き分けとするルールがある．日本将棋連盟は比較的最近（と言っても1983年）この「千日手」の定義を公式に変更している．以前は「同一手順３回」というルールだったがこのルールでは無限に指し手を続けることが可能であるため，現在では「同一局面４回」ということになっている．（旧ルールでは「手順」，新ルールでは「局面」の違いがあることに注意）
改訂のきっかけはその１ヶ月ほど前に行われた名人戦挑戦者決定リーグ第８戦の米長－谷川戦である．このときには同一局面に至る手順が５通り存在し実際に同一局面が９回出現しているが，米長は千日手を回避して勝利に持ち込んだ．ある局面で同一局面に至る２つの手順{0,1}があるとすると，01を反転して10とし，この２つをつなげて0110としても「同一手順３回」にはならない．同様に0110を反転して1001とし，0110に続けて01101001としても「同一手順３回」にはならない．この操作は無限に反復できるから，少なくとも同一局面に至る異なる手順が２つ以上ある場合には，無限に指し続けることが可能になってしまう．
※このことを教えてくれたのは，theory-edge の常連メンバーKlaus D. Witzel である．
※この数列はその後も何度も再発見されている．たとえば1929年にはチェスのグランドマスタで数学教師の Max Euwe がチェスの千日手に関連してこの数列を独自に再発見した．
PTM列には00, 11のような２文字の繰り返しが現れる．これを0=A, 00=B, 1=C, 11=Dのように置き換えて４文字からなる新しい列 "ADACBDBCADACBCADBDACBC..." を得ることができる．この列はもはや繰り返しをまったく持っていない．私はこの無限文字列を「もずさん」の名前にちなんで「数学的モズ歌(Mathematical Mozu Song)」と名付けた※．この文字列の特徴は内部に無限長の回文を含んでいるところにある．たとえば，頭から３文字取るとADA，１１文字取るとADACBDBCADA，43文字取るとADACBDBCADA CBCADBDACB D BCADBDACBC ADACBDBCADAのような回文になっている．これは無限に延長することができるから「数学的モズ歌は無限に長い回文である」という言い方もできる．（数学的モズ歌は無限長の文字列であり，存在するとすれば１個しかないと言ってよいだろう）
※後日もずさんからメールがあり，ＰＴＭ列については『ロジカルな将棋入門』（野崎昭弘、筑摩書房）ですでに言及されていることを知らせてきた．私はＰＴＭ列から派生する非循環無限小数（無理数）をＭＬ上で「モズ数」と呼んでいたが，それも止めて欲しいとの申し出があった．その名称を使い始めてからすでにかなりの本数投稿してしまっていたし，モズというのは一般名詞でもあるのでそのまま使い続けることで了承してもらった．結局私が「モズ数」と呼んでいた数は Prouhet-Thue-Morse定数として知られる数であった．「数学的モズ歌」の方は（私が知る限り）私が第一発見者であると名乗って差し支えないように思われる．
数学的モズ歌はどんな小部分にもまったく繰り返しを含まずかつある意味で左右対称であるような無限文字列であるが，「無限に長い回文」というのは確かにかなり奇妙な代物である．回文の頭と尻尾から一文字づつ取り去っても回文は依然として回文であるから，数学的モズ歌の頭から何文字か取り除き，尻尾からも同じ文字数を取り除くことができれば再び無限長の回文を得られるはずであるが，無限長の文字列の尻尾などというものは存在しないはずだから，どのような操作を行えばよいのか想像することもできない．あえて想像するとすれば，自分の尻尾を飲み込もうとしている蛇のような永劫回帰の構造くらいしか思い浮かばない．
３回以上の反復を含まない文字列をキューブフリー，まったく反復を含まない文字列をスクェアフリーという．このような属性を持つ無限文字列の代表例として以下を挙げることができる．
(1)Prouhet-Thue-Morse: 3-free 2-letters anti-symmetric
(2)Thue: 2-free 3-letters non-symmetric
(3)Mathematical Mozu Song: 2-free 4-letters symmetric
(4)Rivest: 2-free 4-letters non-symmetric
２文字だけからなるスクェアフリー文字列（長さ４以上）が存在しないことは自明である．(1)は上記したアルファベット２文字のキューブフリー無限文字列（PTM列）である．ＰＴＭ列は次のような方法によっても得ることができる．文字Ａから出発し（これをaxiomと呼ぶ）{A→AB, B→BA}の置換操作（endmorphism）を反復する．(2)Ｔhue列はA,B,Cの３文字からなるスクェアフリー文字列である．Ｔhue列はAをaxiomとし，{A→ABC, B→AC, C→B}の反復で生成することができる．(3)は私の発見した数学的モズ歌である※．この列は多少込み入っているが，｛A→ADA, Ｂ→BCB, C→ADCDA, D→BCDCB｝を反復適用することで生成される．このジェネレータを見ればなぜこの文字列が回文になるかは一目瞭然である．
※ここで読者はＤＮＡ鎖を構成する塩基が正確に４個であるという事実を思い出されるのも一興である．ＤＮＡ鎖はご存知のようにA, T, C, G の４種の塩基からなるストリングである．このチェーンはからみあった２重の螺旋構造を取っているが，A⇔T, C⇔Gのような相補関係があることが知られている．我々のモズ歌の場合にも，A⇔Ｄ，Ｂ⇔Ｃの間には完全な相補性を見ることができる．モズ歌のこのような完成美をして究極の mozu-art (Mozart) とする．
(4)はロナルド・リベストのサイトで見つけた４文字からなるスクェアフリー文字列である．リベストが示したのは（上述のＭＭＳ列と同様に）ＰＴＭ列から派生する方法である．ＰＴＭ列を一文字ずらしたものと元のＰＴＭ列を加算する操作で生成することができる．この文字列を生成するジェネレータ（endmorphism）を見つけるのはそれほど難しくない．公理Aから出発し，{A→CB, Ｂ→BA, C→CD, Ｄ→BC}を適用することで生成可能である．私はこのことをメールでリベストに知らせた（９月１８日）．２，３日後にリベストから以下のような返信が届いた．
Hi --
I hope to get a chance to look at your
postings in the near future...
In the meantime, note that my name is "Rivest"
and not "Divest"...
Cheers,
Ron Rivest
ロン（ロナルド）はＲＳＡ暗号アルゴリズムを開発した３人組の一人であり，ＲＳＡの名前はロナルド・リベスト，アディ・シャミア，レオナルド・エーデルマンの頭文字を取ったものである．彼ら３人組はその功績により２００２年のチューリング賞を授与された．（ノーベル数学賞というのは存在しないので，コンピュータ・サイエンスの世界ではチューリング賞と言えばノーベル賞に匹敵する権威がある）私はこの事実を知っていながら，なぜか（魔が差したとしか思えない）Rivest 氏の宛名を間違えて Divest と書いてしまったのだ！divest という単語は「服を脱がせる」とか「離脱」，「剥奪」などおよそろくでもない意味しかない（もちろん―私は後から辞書を引いてそれを知ったのだが）．私は大慌てで「平謝りの手紙」を書いて送ったが，もはや後の祭り．音信はそれきりふっつりと途絶えてしまった．．．
【参照リンク】馬場研究所→Mathematical Mozu Song
→An Infinitely Palindromic Square-Free Sequence
←人気ブログランキングにご協力を！
←ご協力お願いします！ 将棋では指し手が堂々巡りするような盤面を「千日手」と称して引き分けとするルールがある．日本将棋連盟は比較的最近（と言っても1983年）この「千日手」の定義を公式に変更している．以前は「同一手順３回」というルールだったがこのルールでは無限に指し手を続けることが可能であるため，現在では「同一局面４回」ということになっている．（旧ルールでは「手順」，新ルールでは「局面」の違いがあることに注意）
改訂のきっかけはその１ヶ月ほど前に行われた名人戦挑戦者決定リーグ第８戦の米長－谷川戦である．このときには同一局面に至る手順が５通り存在し実際に同一局面が９回出現しているが，米長は千日手を回避して勝利に持ち込んだ．ある局面で同一局面に至る２つの手順{0,1}があるとすると，01を反転して10とし，この２つをつなげて0110としても「同一手順３回」にはならない．同様に0110を反転して1001とし，0110に続けて01101001としても「同一手順３回」にはならない．この操作は無限に反復できるから，少なくとも同一局面に至る異なる手順が２つ以上ある場合には，無限に指し続けることが可能になってしまう．
※このことを教えてくれたのは，theory-edge の常連メンバーKlaus D. Witzel である．
※この数列はその後も何度も再発見されている．たとえば1929年にはチェスのグランドマスタで数学教師の Max Euwe がチェスの千日手に関連してこの数列を独自に再発見した．
PTM列には00, 11のような２文字の繰り返しが現れる．これを0=A, 00=B, 1=C, 11=Dのように置き換えて４文字からなる新しい列 "ADACBDBCADACBCADBDACBC..." を得ることができる．この列はもはや繰り返しをまったく持っていない．私はこの無限文字列を「もずさん」の名前にちなんで「数学的モズ歌(Mathematical Mozu Song)」と名付けた※．この文字列の特徴は内部に無限長の回文を含んでいるところにある．たとえば，頭から３文字取るとADA，１１文字取るとADACBDBCADA，43文字取るとADACBDBCADA CBCADBDACB D BCADBDACBC ADACBDBCADAのような回文になっている．これは無限に延長することができるから「数学的モズ歌は無限に長い回文である」という言い方もできる．（数学的モズ歌は無限長の文字列であり，存在するとすれば１個しかないと言ってよいだろう）
※後日もずさんからメールがあり，ＰＴＭ列については『ロジカルな将棋入門』（野崎昭弘、筑摩書房）ですでに言及されていることを知らせてきた．私はＰＴＭ列から派生する非循環無限小数（無理数）をＭＬ上で「モズ数」と呼んでいたが，それも止めて欲しいとの申し出があった．その名称を使い始めてからすでにかなりの本数投稿してしまっていたし，モズというのは一般名詞でもあるのでそのまま使い続けることで了承してもらった．結局私が「モズ数」と呼んでいた数は Prouhet-Thue-Morse定数として知られる数であった．「数学的モズ歌」の方は（私が知る限り）私が第一発見者であると名乗って差し支えないように思われる．
数学的モズ歌はどんな小部分にもまったく繰り返しを含まずかつある意味で左右対称であるような無限文字列であるが，「無限に長い回文」というのは確かにかなり奇妙な代物である．回文の頭と尻尾から一文字づつ取り去っても回文は依然として回文であるから，数学的モズ歌の頭から何文字か取り除き，尻尾からも同じ文字数を取り除くことができれば再び無限長の回文を得られるはずであるが，無限長の文字列の尻尾などというものは存在しないはずだから，どのような操作を行えばよいのか想像することもできない．あえて想像するとすれば，自分の尻尾を飲み込もうとしている蛇のような永劫回帰の構造くらいしか思い浮かばない．
３回以上の反復を含まない文字列をキューブフリー，まったく反復を含まない文字列をスクェアフリーという．このような属性を持つ無限文字列の代表例として以下を挙げることができる．
(1)Prouhet-Thue-Morse: 3-free 2-letters anti-symmetric
(2)Thue: 2-free 3-letters non-symmetric
(3)Mathematical Mozu Song: 2-free 4-letters symmetric
(4)Rivest: 2-free 4-letters non-symmetric
２文字だけからなるスクェアフリー文字列（長さ４以上）が存在しないことは自明である．(1)は上記したアルファベット２文字のキューブフリー無限文字列（PTM列）である．ＰＴＭ列は次のような方法によっても得ることができる．文字Ａから出発し（これをaxiomと呼ぶ）{A→AB, B→BA}の置換操作（endmorphism）を反復する．(2)Ｔhue列はA,B,Cの３文字からなるスクェアフリー文字列である．Ｔhue列はAをaxiomとし，{A→ABC, B→AC, C→B}の反復で生成することができる．(3)は私の発見した数学的モズ歌である※．この列は多少込み入っているが，｛A→ADA, Ｂ→BCB, C→ADCDA, D→BCDCB｝を反復適用することで生成される．このジェネレータを見ればなぜこの文字列が回文になるかは一目瞭然である．
※ここで読者はＤＮＡ鎖を構成する塩基が正確に４個であるという事実を思い出されるのも一興である．ＤＮＡ鎖はご存知のようにA, T, C, G の４種の塩基からなるストリングである．このチェーンはからみあった２重の螺旋構造を取っているが，A⇔T, C⇔Gのような相補関係があることが知られている．我々のモズ歌の場合にも，A⇔Ｄ，Ｂ⇔Ｃの間には完全な相補性を見ることができる．モズ歌のこのような完成美をして究極の mozu-art (Mozart) とする．
(4)はロナルド・リベストのサイトで見つけた４文字からなるスクェアフリー文字列である．リベストが示したのは（上述のＭＭＳ列と同様に）ＰＴＭ列から派生する方法である．ＰＴＭ列を一文字ずらしたものと元のＰＴＭ列を加算する操作で生成することができる．この文字列を生成するジェネレータ（endmorphism）を見つけるのはそれほど難しくない．公理Aから出発し，{A→CB, Ｂ→BA, C→CD, Ｄ→BC}を適用することで生成可能である．私はこのことをメールでリベストに知らせた（９月１８日）．２，３日後にリベストから以下のような返信が届いた．
Hi --I hope to get a chance to look at your
postings in the near future...
In the meantime, note that my name is "Rivest"
and not "Divest"...
Cheers,
Ron Rivest
ロン（ロナルド）はＲＳＡ暗号アルゴリズムを開発した３人組の一人であり，ＲＳＡの名前はロナルド・リベスト，アディ・シャミア，レオナルド・エーデルマンの頭文字を取ったものである．彼ら３人組はその功績により２００２年のチューリング賞を授与された．（ノーベル数学賞というのは存在しないので，コンピュータ・サイエンスの世界ではチューリング賞と言えばノーベル賞に匹敵する権威がある）私はこの事実を知っていながら，なぜか（魔が差したとしか思えない）Rivest 氏の宛名を間違えて Divest と書いてしまったのだ！divest という単語は「服を脱がせる」とか「離脱」，「剥奪」などおよそろくでもない意味しかない（もちろん―私は後から辞書を引いてそれを知ったのだが）．私は大慌てで「平謝りの手紙」を書いて送ったが，もはや後の祭り．音信はそれきりふっつりと途絶えてしまった．．．
【参照リンク】馬場研究所→Mathematical Mozu Song
→An Infinitely Palindromic Square-Free Sequence
←人気ブログランキングにご協力を！
by exod-US
| 2006-11-24 18:40
| 金正日ミサイル乱射事件
