nabeshinによる
2007年10月29日 11時28分の掲載
二十歳を過ぎた、ただの人部門より。
二十歳を過ぎた、ただの人部門より。
あるAnonymous Coward 曰く、
WIRED VISIONの記事のよれば、Wolfram氏が提案したもっとも簡単なチューリングマシンが万能チューリングマシンであることを20歳のイギリスの学生が証明して見せたのこと。Wolfram氏は、この証明に2万5000ドルの賞金をかけており、見事47日後に証明して見せた。
ちなみに、Wolfram氏は、複雑系理論の権威でもあり、Wolfram Mathematicaの設立者でもある。社名の通り、Mathematicaを開発している会社だ。
提案されたチューリングマシンは、2つの状態と3つの色を持つ装置であり、証明の内容(PDF)も公開されているので、興味のある方は追ってみてはいかがでしょうか？
この議論は賞味期限が過ぎたので、保存されている。
新たにコメントを書くことはできない。
【速報】「証明」に誤り発見かも (スコア:5, 興味深い)
ええええええええ！Σ（゜д゜;）
Re:【速報】「証明」に誤り発見かも (スコア:5, 参考になる)
本家でも突っ込まれていますが。(#21165401 [slashdot.org])
「証明」に誤りが見つかったことそれ自体は別に驚くようなことではないと思いますが、こんなに早く覆ったということには驚いています。もしや、専門家の査読なしで「証明された」と公表してしまったのでは…という疑念がフツフツと…。
で、この公表を受けて「まじ！？」と専門家が証明をチェックして、すぐに誤りを発見、と。そんなところじゃないですかね。
親コメント
もう少し正確に言うと、 (スコア:4, 参考になる)
Wolframが提案したのは2つの状態と3つの色を持つチューリングマシンで、
今回の結果によって、今のところ「最も単純な」万能チューリングマシンとなったのだそうです。
Re:もう少し正確に言うと、 (スコア:4, 参考になる)
と、いうことのようですね。→「2つの状態と3つの色を持つ装置は（現時点で知られる限り最小の）万能チューリングマシンである」
本家WIRED NEWS [wired.com]でもそのような表現になっています。
# それ以前では、「万能チューリングマシンを構成するためには、2つの状態と5つの色を持てば十分」という上限までが分かっていたようで。
# （このときもWolfram氏は予想だけ）
が、WIRED VISION日本語版の記事の表現だと、「最少の万能チューリングマシンは、2つの状態と3つの色を持てばよく、それ以下では成り立たない」ことが証明されたように読めてしまいますね。
「ウルフラム氏のチューリングマシン」を20歳の学生が証明 [wiredvision.jp] （強調部は引用者）
翻訳の工程で"yet"が抜けてるような。あるいは、翻訳者が重要だと思わなかったか。
親コメント
Re:もう少し正確に言うと、 (スコア:5, 参考になる)
親コメント
Re:もう少し正確に言うと、 (スコア:3, 参考になる)
メモリ（テープ）に書き込む内容が色にあたります。3色あるので、1ビットに 0,1,2を書き込む、と考えることができます。
2が気持ち悪ければ、2ビットに 00,01,10 を書き込んでそれを1つのまとまり（セル）とみなしても構いません。
他に、現在どこのメモリを読んでいるかを表すプログラムカウンタのようなもの（ヘッド）があります。
普通のコンピュータのメモリ（や通常のチューリングマシンのテープ）と違うのは、
縦方向と横方向の両方にメモリが無限大にのびているということです。
さらに、可能な動作（プログラムの仕方）も普通のコンピュータとは異なります。
縦方向、横方向の番地を便宜上 [3, 8] のように表すとします（縦3番地、横8番地）。
ソースコードには次のような文字列が複数行書かれています。
(a, b) -> (c, d, e)
(f, g) -> (h, i, j)
...
一行目は、プログラムカウンタが [x, y] 番地を指しているとすると、
[x, y] 番地の内容（色）を読みとり、もしその色が a で、レジスタの状態が b なら、
プログラムカウンタを [x + 1, y + e] に更新し、その位置に色 c を書き込み、
レジスタの状態を d にするということを表します。e は 0, 1, -1 のいずれかしかとりません。
わかりにくい記述ですが、要は、一回の動作でカウンタの位置のメモリを読み取り、
縦に 1 進み、横に 1 か 0 か -1 進み、進んだ場所に決められた色を書き込むということです。
親コメント
Re:もう少し正確に言うと、 (スコア:2, 参考になる)
気になったのでちょっと賞のサイトで確認してきました．
読めば分かるんですが，横方向両側に無限というだけで縦方向は1マスしかないです．
微妙に違います．
(a, b) -> (c, d, e)
という状態遷移関数に従った動作は以下です．
ステップの直前にヘッドがy番地にあるとします．y番地の色がaで内部状態がbだったとすると，y番地の色をcにして状態をdにしてヘッドをy+eに移動します．あとeは1か-1のみです．
移動してから色を塗るんじゃなくって，移動前に色を塗ります．
親コメント
いっぱいあるな (スコア:3, すばらしい洞察)
スピンの上下と３色だからクォークだな。
Re:いっぱいあるな (スコア:5, おもしろおかしい)
#まあSFのネタくらいにはなるか
親コメント
Re:いっぱいあるな (スコア:4, 興味深い)
情報理論における各種制限（最大情報量、エントロピーやら何やら）を適用してやることで現実の
物理系における物理量がとり得る最大値などの制限範囲を求めたり、というような研究があります。
その立場で行けば、宇宙そのものも膨大な演算量と記憶容量を持つ(量子的な過程も含む)システム
でしかなく、量子情報理論によってその演算範囲等が求まる巨大な計算機です。
#見方の違いであり、巨大な計算機として捉えても、多数の粒子の集合体と捉えても等価。ただ、
#解こうとする問題によってどちらのアプローチの方が楽かが違う。ある映像を考えるのに、実像で
#あらわしてもそのフーリエ変換で表しても表現しているものは一緒、でも使い道によってはどちらか
#の方がもう一方より楽、というのと近いような感じか。
なお、宇宙のサイズが有限であることや(因果の地平線により規定され、時間とともに拡大)、
エントロピーの増大により最大計算時間に制限がある(いずれ熱的死に向かうので無限時間の演算は
不可能)という事から、有限の計算能力しか持てず、万能チューリングマシンとはなりえません。
親コメント
Re:いっぱいあるな (スコア:2, 興味深い)
親コメント
Re:いっぱいあるな (スコア:4, おもしろおかしい)
親コメント
Re:いっぱいあるな (スコア:3, おもしろおかしい)
# なんてなー。
親コメント
「誰かこれ証明して。名前は俺のをつけるから」 (スコア:1)
金持ちの道楽文化活動の誕生ですか？Re:「誰かこれ証明して。名前は俺のをつけるから」 (スコア:2, すばらしい洞察)
エルデシュも若い人の育成の意味も込めて、たくさんの賞金の付いた問題を発表しています。
それに本質的な問題を考えることは、誰にでも出来る簡単なことでは無いと思いますよ。
親コメント
A New Kind of Science の邦訳はまだか… (スコア:1)
それに引きかえA New Kind of Science [nikkeibp.co.jp]をいつか読もういつか読もうと思いながら歳を重ねる我が身のなさけなさよ…
いや、すでに無償公開 [wolframscience.com]されているんで誰でも読めんですけど、私にゃさっぱりです。
＃ ちなみに A New Kind Of Science がオンライン公開された時の本家/.の記事 [slashdot.org]
Flatearther だけが良い fundamentalist である
Wolfram Mathematicaって．．． (スコア:1, 参考になる)
この明らかな間違いは直した方が良いかと．．．
会社概要は「http://www.wolfram.co.jp/company/background.html [wolfram.co.jp]」で見られます．