2

与えられた n 状態のビジー ビーバー ゲームについて、ビジー ビーバー関数は一意ですか、それとも最大スコアが同じ複数の関数が存在する可能性がありますか? おそらく、どちらの方法でも証明されていませんか？

4

3 に答える 3

3

はい、そうです。

ビジー ビーバー関数は次のように定義されます。

\Sigma(n) = max { \sigma(M) | M is a halting n-state 2-symbol Turing machine}

存在する場合、最大値は一意です (ラドーはこれを証明しました)。これは単なる数字です。

したがって、\Sigma(n) も一意であり、離散関数 \Sigma: N --> N も一意です。\Sigma を連続関数に拡張する方法は複数あるかもしれませんが、なぜ誰かがこれをやりたいのかは私には理解できません。

\Sigma の小さな値を計算することは可能です。既知の最大値については、 OEIS エントリを確認してください。

于 2011-09-06T14:34:54.850 に答える
2

@PengOne が指摘したように、この機能は確かにユニークです。これは完全に定義された N -> N 離散関数です。

ただし、定式化から (または、「同じ最大スコアを持つ関数が複数存在する可能性があります」)、同じ最大値を与えるビジー ビーバーが複数存在するかどうかを知りたいことも理解できます。その場合、はい、N を指定すると、少なくとも 2 つのビジー ビーバーが存在し、シフトを逆にするだけで一方が他方から構築されます。

于 2011-09-06T14:54:44.100 に答える
1

これはずっと前に尋ねられましたが、私はこれが興味深いと思いました: http://www.win.tue.nl/~wijers/shallit.pdf

また、3 ステート ビジー ビーバー問題をブルート フォースするアルゴリズムをコーディングしたところ、6 つのシンボル (連続的または非連続的) を生成する約 22 の非対称構成が得られました。これは、状態 1 と状態 2 を入れ替えたり、最初の遷移を逆にしたりできると考えると、おそらく 60 ほどの構成があることを意味します。

しかし、それは生成されたシンボルの量のみであり、「最長実行」のものではありません。

于 2014-04-15T20:32:27.433 に答える