忙しいビーバーの課題が解決

最近では、コンピュータサイエンスの成果を記録することは、人工知能の最新の進歩を語ることにまで縮小されています。7月2日、 30年以上前の仮説の証明の発表 この連祷を混乱させるようになった。さらに、この悪用は、 アメリカのメディアが伝えた クアンタ 雑誌学術界や産業界から出たものではありません。約20名の国際チームが遠隔で協力し、部分的に これらはすべて「アマチュア」の集まりで、若いフランス人トリスタン・ステリンによって結成されました。

ソフトウェア会社の共同創設者 広報彼は2022年3月、何度も試行錯誤した問題を解くという挑戦を開始しました。それは、16兆以上のコンピュータプログラムの中から、どのプログラムが答えを出すのをやめるかを知り、永遠に続く「役に立たない」プログラムを排除することです。そして何よりも、最も多くのステップを踏んだ後に止まる希少な真珠を見つけることです。この問題は、動物の美徳に敬意を表して、ハンガリーの数学者ティボール・ラドによって1962年に「忙しいビーバー競争」と名付けられました。

「まるでポケモンを狩っているみたい！」 トリスタン・ステリンは冗談を言う。何がポイントなのでしょう？この「ゲーム」は、単純さから複雑さが生まれることを示し、数学とコンピュータサイエンスの深遠な疑問に触れています。

チューリングリボン

この問題を理解するには、いくつかの注意が必要です。1936年、イギリスのアラン・チューリングは、単純な「ディスプレイ「hello」」から、巨大なChatGPTなどの最も複雑なものまで、あらゆるプログラムを彼の名前を冠した機械、リボンで「簡単に」表現できることを実証しました。 無限で、読み取り/書き込みヘッドの下を通過するときに 0 または 1 でマークされます。ヘッドは、0 または 1 のシンボルを変更したり、テープを 1 マス進めたり巻き戻したり、状態を変更したりすることしかできません。この「状態」には、3 つの命令 (0 または 1 を書き込む、進める/巻き戻す、状態を変更する) が含まれており、マシンのソフトウェアです。1 つ、2 つ、またはそれ以上のプログラムを持つことができます。単一状態のマシンは、25 種類のプログラムを生成できます。1 から 2 までで 6,561 通り、1 から 5 までで 16 兆通り以上になります。

この概念により、チューリングは、他のプログラムが停止するかどうかを指示するプログラムを見つけることは不可能であることを示しています。ビジービーバー問題（” 忙しいビーバー 「最大の有用なプログラム」（英語ではBBと略される）は、別の不可能性を提示します。それは、リボンを最も多く動かしてから停止して答えを出すプログラムです。Tibor Radoは、この機能は計算不可能であることを実証しました。一連の操作でこれらすべての値を見つけることは不可能です。

この記事の残り 57.18% を読む必要があります。残りは購読者向けに予約されています。