2016-赤と青のボール-解説
- 考案国: イタリア
- 正解
- 「 ゲームが終わらないのは、『一番下が青』である4通りの並びです」
- 「 ゲームが終わらないのは、『一番下が青』である4通りの並びです」
- 説明
- 次のように，一番下（左から3番目）が青（B）のときは，ボタンを押していくうちに「RBRRBR」になります．
BBB→RBRB→RBRRB→RBRRBR
BRB→RBRB→RBRRB→RBRRBR
RBB→RBRR→BRB→RBRB→RBRRB→RBRRBR
RRB→RBRR→BRB→RBRB→RBRRB→RBRRBR - 「RBRRBR」というパターンは、ボタンを押していくうちに「RBRRBR」に戻りいつまでも終わりになりません．
RBRRBR→BRBRR→BBRB→RBRBB→RBRRBR
- 次のように，一番下（左から3番目）が青（B）のときは，ボタンを押していくうちに「RBRRBR」になります．
- 解説
- このパズルは，Emil Leon Post により提案された文字列の書き換えを用いた計算モデル "Post production system" を題材にしています．
Post は 1920 年代に草案したものの，公表されたのは 1943 年です．
Emil Leon Post (1897-1954) はポーランド生まれのアメリカ人で，計算可能性理論の草創期に活躍した数学者であり論理学者です． - 書き換え系 (rewriting system) は，式や文字列などのある部分を別のものに置き換えるシステム（系）です．
書き換えモデルは，オブジェクト（操作対象）とそれに対する適用可能な操作や変形を定義する関係の有限集合からなるシステム（系）と見なすことができます． - 文脈自由文法 (CFG) などの形式文法も書き換え系の一種です．
例えば，乗法と加法の系はわずかの規則からなる文脈自由文法で定義できます．
- このパズルは，Emil Leon Post により提案された文字列の書き換えを用いた計算モデル "Post production system" を題材にしています．
注があるものを除き, このサイトの内容物は
