トップ «前の日記(2008-02-22) 最新次の日記(2008-02-24)» 編集

日々の破片

著作一覧

2008-02-23

_ 有限状態機械

昨日の本の続きで、第2章は有限状態機械についてだ。

思考する機械コンピュータ (サイエンス・マスターズ)(ダニエルヒリス)

有限状態機械は、ネットワークプロトコルを実装する必要があったので、ずいぶん以前から親しんでいるのだが、これも問題が出てきて、やはり僕には簡単ではなかった。

問題はミンスキーがMITで筆者に教えた「一斉射撃問題」だ。

司令官が銃を手にした兵士たちを一列横隊に整列させ、銃殺刑を執行させようとしている。しかし、兵士たちの数があまりにも多く、[簡略して書くと、司令官が怒鳴っても声が最後の兵士までは届かない。したがって、列の先頭の兵士に命令を下す。兵士は同様に、隣の兵士には命令を伝えられる。]ただし、兵士たちは一斉に射撃しなければならない。背後では太鼓が規則的に鳴らされているが、兵士の総数がわからないので、「太鼓が何回鳴ったところで一斉に射撃せよ！」といった命令は下せない。兵士は自分の両隣の兵士に何を言ってもかまわないが、射撃はすべての兵士が一斉にしなければならない。

ヒントとして、片手に満たない有限状態機械を作って解ける、と出ている。

以下に、Rubyで僕が書いたプログラムだが、本当にこの方法（状態の切り出し）で良いかは自信がない。状態は4個に収まっているが、射撃をする状態は独立しているべきなのではないか、とか、伝達内容は本当にこれで題意を取っているのか、が、わからないからだ。

もう一点あって、これを書いて気づいたが、Rubyではあまりきれいに書けないか、または僕がきれいな書き方がわからない。Cなら関数ポインタの状態遷移表、Javaならインナークラスの状態遷移表を作るところだが、Rubyだと表を作る気になれないからだ。

class Soldier
  def initialize
    @state = idle
  end
  def pulse(left, right)
    @state.call(left, right)
  end
  def prepare(count)
    @count = count
    @state = prepare_next
  end
  def start_count_down
    @state = prepare_count_down
  end
  private
  def idle
    Proc.new do |left, right|
    end
  end
  def prepare_next
    Proc.new do |left, right|
      if right
        right.prepare(@count + 1)
        @state = idle
      else
        @state = prepare_count_down
      end
    end
  end
  def prepare_count_down
    Proc.new do |left, right|
      if left
        left.start_count_down
      end
      @state = count_down
    end
  end
  def count_down
    Proc.new do |left, right|
      if @count == 0
        puts 'bang!'
        @state = idle
      else
        @count -= 1
      end
    end
  end
end
NUMBER_OF_SOLDIERS = 20
s = [nil]
1.upto(NUMBER_OF_SOLDIERS) do |i|
  s << Soldier.new
end
s << nil
s[1].prepare 1
x = 1
while true
  puts "round # #{x}"
  1.upto(NUMBER_OF_SOLDIERS) do |i|
    s[i].pulse(s[i - 1], s[i + 1])
  end
  x += 1
  break if x > NUMBER_OF_SOLDIERS + 10
end

このプログラムでは、兵士が20人いれば、太鼓が23回叩かれたところで一斉射撃が起きる。

状態は4つあるprivateメソッドで示されている。pulseメソッドは太鼓の音によって実行される。

追記：これはだめだな。23回で射撃するというのはおかしい。隣の兵士への伝言を1回で全部やってしまっているけど、それは無理だ。たまたま、同時に遷移が行われるような作り方をしているからだな。というわけで、後で直す。と思ったけど左から右を直すと、右から左への通信が1太鼓分遅延するようになるから、配列使って順にまわす限りそこにこだわっても意味がないことがわかったのでやめた。

追記：別解。逃げ出したら（一歩を踏み出したら）、撃つってのも良いかも。もちろん死刑囚にはそれを教えていない。彼は気づくと、すべての縛めから解放された状態で壁の前に立たされている。しかし、もし観念していたら、永遠のデッドロックとなる。