とある問題を考えていたら、パズルに出会ったのですが、僕はパズルが苦手なので、どなたか代わりに考えてください(苦笑)。
k個のメモリセルと1種類の機械語命令を持つ“マシン”を考えます。
- メモリセルにはアドレスを付けます。ここでは番号付けを1番からはじめて、1, 2, ..., k がアドレスだとします。0からが好きなら、そうしてもけっこう。
- iは、1からk-1のアドレスのどれかとして、機械語命令は s.i の形。その意味は、セルiの内容とセル(i+1)の内容を交換すること。
例えばメモリセルは4個だとして、その内容が AABB だったとします。次の命令列を実行してみます。
- s.2, s.1, s.3, s.2
次のように状態遷移します。
AABB
s.2
ABAB
s.1
BAAB
s.3
BABA
s.2
BBAA
さて、このマシンはマルチコア(?)だとします。同時に複数の命令を実行できます。同時実行はブラケットで囲って示しましょう。
- s.2, [s.1, s.3], s.2
次のように状態遷移します。
AABB
s.2
ABAB
s.1, s.3
BABA
s.2
BBAA
命令列「s.2, [s.1, s.3], s.2」において、[s.1, s.3]は1クロックサイクルで実行されるので、命令列全体＝プログラムは3ステップと考えます。s.i と s.j で、iとjが隣り合っていなければ同時並列実行できます。いくらでも好きなだけ並列実行していいとします。
以上の条件のもとで次の問題を考えます。
k = n + m として、メモリの最初の状態は、Aがn個、Bがm個並んでいるとします。この状態を AnBm と書きます。まず、これをBmAn に直すには、最小何ステップかかるでしょうか？ というのが1つ目の問題。
次に、最小ステップでも、そうでなくてもいいのですが、AnBm → BmAn と状態遷移させるプログラムの一般形を、n と m を含むなんらかの表現として書き下ししてください -- とっても曖昧な表現ですが、表現はできるだけキレイな形を希望。これが2つ目の問題です。
僕がほんとに欲しいのは“キレイな形”の表現です。
[追記]
oto-oto-otoさんからトラックバックをいただきました。マヤゲームとヤング図か、面白いなー。
このパズルには、誰でも思いつく一般化がいくつかあります。
- 文字の数を増やす。
- 初期状態と終状態を任意の文字列（メモリ状態）にする。
- リング状のメモリを考える（k番目のセルの次に1番目のセルが来るとする）。
- 左または右に無限なメモリ、あるいは両側に無限なメモリを考える。
基本命令を増やす方向では、入れ替えを2種類考えることができます。
要するにブレイドの話になります。文字を色だと思うと、紐とか釘が何色かに塗られたブライドですね。
命令数（交差の数）とステップ数（ブレイドの段数）に関して最適化が考えられますが、最適化は何らかのコスト関数の値を減らす方向での同値変形です。同値変形の背景は、ライデマイスター移動だのヤン・バクススター方程式だのでしょう。
このテの話は、簡単なんだか難しいんだか（僕には）予測できないので、面白そうだけど手を出しにくいなー。深入りするのはやめよう、っと。
[/追記]
[追記の追記]
似たようなことを、ナプキンに描いて考えてたとき：
[/追記の追記]
