WIRED VISIONの記事のよれば、Wolfram氏が提案したもっとも簡単なチューリングマシンが万能チューリングマシンであることを20歳のイギリスの学生が証明して見せたのこと。Wolfram氏は、この証明に2万5000ドルの賞金をかけており、見事47日後に証明して見せた。 ちなみに、Wolfram氏は、複雑系理論の権威でもあり、Wolfram Mathematicaの設立者でもある。社名の通り、Mathematicaを開発している会社だ。 提案されたチューリングマシンは、2つの状態と3つの色を持つ装置であり、証明の内容(PDF)も公開されているので、興味のある方は追ってみてはいかがでしょうか?
セルオートマトンの歴史 セルオートマトンはもともと1940年代末に生物の自己複製機能を摸擬するために、数学者のウラムとフォン・ノイマンによって提案されたものです[Ne66]。ウラムはモンテカルロ法という計算機シミュレーション法を開発したことで知られています。また彼は水素爆弾の製造にもかかわりました。フォン・ノイマンは最も有名な数学者の一人で、ゲーム理論の創始者[Po92]、史上初の電子計算機の設計者として知られています。当時フォン・ノイマンは機械またはオートマトン(自動機械と訳される)が自分自身のレプリカを作ることができるかどうかについて研究していました。彼は、自己複製には機械自身が自分自身の設計図(ブループリント)を有しており、それを複製することができれば自分自身を複製できると結論づけました。無論、このブループリントは実際の生物でDNA(一部のウィルスではRNA)に対応します。ただし、こ
この記事には参考文献や外部リンクの一覧が含まれていますが、脚注による参照が不十分であるため、情報源が依然不明確です。 適切な位置に脚注を追加して、記事の信頼性向上にご協力ください。(2022年3月) セル・オートマトンの一種ライフゲームで、ゴスパー(英語版)のグライダー銃がグライダーを放っているところ[1] セル・オートマトン(英: cellular automaton、略称:CA)とは、格子状のセルと単純な規則による、離散的計算モデルである。 計算可能性理論、数学、物理学、複雑適応系、数理生物学、微小構造モデリングなどの研究で利用される。非常に単純化されたモデルであるが、生命現象、結晶の成長、乱流といった複雑な自然現象を模した、驚くほどに豊かな結果を与えてくれる。 正確な発音に近いセルラ・オートマトンとも呼ばれることがある。セルは「細胞」「小部屋」、セルラは「細胞状の」、オートマトンは「
A universal Turing machine is powerful enough to emulate any standard computer. The question is: how simple can the rules for a universal Turing machine be? Since the 1960s it has been known that there is a universal 7,4 machine. In A New Kind of Science, Stephen Wolfram found a universal 2,5 machine, and suggested that the particular 2,3 machine that is the subject of this prize might be universa
「ウルフラム氏のチューリングマシン」を20歳の学生が証明 2007年10月26日 サイエンス・テクノロジー コメント: トラックバック (0) Brandon Keim 2007年10月26日 複雑系理論の権威であるStephen Wolfram氏が、あるチューリングマシンを提案し、これが考えられるありとあらゆる計算問題を解く能力を持つ、考え得る限りで最も単純なコンピューターであることを証明するよう呼びかけた。 それからわずか47日後、イギリスのバーミンガム大学コンピューター科学部の学生Alex Smithさん(20歳)が、見事にこれを証明して見せた。 チューリングマシンは、コンピューターの世界に偉大な貢献をした数学者、アラン・チューリングが1936年に提案したものだ。 今ではハードウェアをソフトウェアと切り離すことは当たり前になっているが、チューリングはこれを理論として考え出した最初の1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く