「ウルフラム氏のチューリングマシン」の万能性を20歳の学生が証明 39
ストーリー by nabeshin
二十歳を過ぎた、ただの人 部門より
二十歳を過ぎた、ただの人 部門より
あるAnonymous Coward 曰く、
WIRED VISIONの記事のよれば、Wolfram氏が提案したもっとも簡単なチューリングマシンが万能チューリングマシンであることを20歳のイギリスの学生が証明して見せたのこと。Wolfram氏は、この証明に2万5000ドルの賞金をかけており、見事47日後に証明して見せた。
ちなみに、Wolfram氏は、複雑系理論の権威でもあり、Wolfram Mathematicaの設立者でもある。社名の通り、Mathematicaを開発している会社だ。
提案されたチューリングマシンは、2つの状態と3つの色を持つ装置であり、証明の内容(PDF)も公開されているので、興味のある方は追ってみてはいかがでしょうか？
【速報】「証明」に誤り発見かも (スコア:5, 興味深い)
ええええええええ！Σ（゜д゜;）
Re:【速報】「証明」に誤り発見かも (スコア:5, 参考になる)
本家でも突っ込まれていますが。(#21165401 [slashdot.org])
「証明」に誤りが見つかったことそれ自体は別に驚くようなことではないと思いますが、こんなに早く覆ったということには驚いています。もしや、専門家の査読なしで「証明された」と公表してしまったのでは…という疑念がフツフツと…。
で、この公表を受けて「まじ！？」と専門家が証明をチェックして、すぐに誤りを発見、と。そんなところじゃないですかね。
Re:【速報】「証明」に誤り発見かも (スコア:1)
the.ACount
もう少し正確に言うと、 (スコア: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:もう少し正確に言うと、 (スコア:1)
Wolfman氏のBlog [wolfram.com]にも次のように書いてあります。
We know that no 2,2 machine can be universal. So the simplest possibility is 2,3.
Re:もう少し正確に言うと、 (スコア:1)
Re:もう少し正確に言うと、 (スコア:0)
○ wolfram
Re:もう少し正確に言うと、 (スコア:1)
状態が0と1として、色にあたるのって何なんでしょう?
それとも、色が0と1で、状態がメモリアドレスのようなものにあたる?
1を聞いて0を知れ!
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のみです．
移動してから色を塗るんじゃなくって，移動前に色を塗ります．
Re:もう少し正確に言うと、 (スコア:1)
3色のオートマトン (スコア:1)
今回の成果は、状態2・色3のチューリングマシンさえあれば、他のどんなチューリングマシン──例えば5状態・256色のチューリングマシンでも──シミュレートできる、ってことかと。
私も門外漢なので識者のツッコミ希望。
# 「オレは、外人とプログラム言語で意思疎通したことあるぜ」という猛者は、ぜひ証明のpdfをお読みください。
# perlで語られているので。:-)
Re:もう少し正確に言うと、 (スコア:1)
最低でも２の100乗くらいあるだろう。
the.ACount
Re:もう少し正確に言うと、 (スコア:0)
多分、そうだと思います。
Re:もう少し正確に言うと、 (スコア:0)
いっぱいあるな (スコア:3, すばらしい洞察)
スピンの上下と３色だからクォークだな。
Re:いっぱいあるな (スコア:5, おもしろおかしい)
#まあSFのネタくらいにはなるか
Re:いっぱいあるな (スコア:4, 興味深い)
情報理論における各種制限（最大情報量、エントロピーやら何やら）を適用してやることで現実の
物理系における物理量がとり得る最大値などの制限範囲を求めたり、というような研究があります。
その立場で行けば、宇宙そのものも膨大な演算量と記憶容量を持つ(量子的な過程も含む)システム
でしかなく、量子情報理論によってその演算範囲等が求まる巨大な計算機です。
#見方の違いであり、巨大な計算機として捉えても、多数の粒子の集合体と捉えても等価。ただ、
#解こうとする問題によってどちらのアプローチの方が楽かが違う。ある映像を考えるのに、実像で
#あらわしてもそのフーリエ変換で表しても表現しているものは一緒、でも使い道によってはどちらか
#の方がもう一方より楽、というのと近いような感じか。
なお、宇宙のサイズが有限であることや(因果の地平線により規定され、時間とともに拡大)、
エントロピーの増大により最大計算時間に制限がある(いずれ熱的死に向かうので無限時間の演算は
不可能)という事から、有限の計算能力しか持てず、万能チューリングマシンとはなりえません。
Re:いっぱいあるな (スコア:2, 興味深い)
Re:いっぱいあるな (スコア:1)
the.ACount
Re:いっぱいあるな (スコア:0)
Re:いっぱいあるな (スコア:4, おもしろおかしい)
Re:いっぱいあるな (スコア:3, おもしろおかしい)
# なんてなー。
Re:いっぱいあるな (スコア:1)
＃最近はもう誤変換じゃなく普通に手書きで間違って書かれるのを目にすることが多くなって悲しい。
Re:いっぱいあるな (スコア:0)
Re:いっぱいあるな (スコア:1)
信号機と赤、黄、緑(青)の三色とON OFFとどう違うのかわからなかった。
向こうは、2の素子が3つの色を発し、それが2の状態を持つと見えたんです。
# 源ネタは、この人の本 [google.co.jp]とおもぼしきもので良いでしょうか。
がんばろう。と自分に言い聞かせる。
「誰かこれ証明して。名前は俺のをつけるから」 (スコア:1)
金持ちの道楽文化活動の誕生ですか？Re:「誰かこれ証明して。名前は俺のをつけるから」 (スコア:2, すばらしい洞察)
エルデシュも若い人の育成の意味も込めて、たくさんの賞金の付いた問題を発表しています。
それに本質的な問題を考えることは、誰にでも出来る簡単なことでは無いと思いますよ。
Re:「誰かこれ証明して。名前は俺のをつけるから」 (スコア:1)
Re:「誰かこれ証明して。名前は俺のをつけるから」 (スコア:1)
A New Kind of Science の邦訳はまだか… (スコア:1)
それに引きかえA New Kind of Science [nikkeibp.co.jp]をいつか読もういつか読もうと思いながら歳を重ねる我が身のなさけなさよ…
いや、すでに無償公開 [wolframscience.com]されているんで誰でも読めんですけど、私にゃさっぱりです。
＃ ちなみに A New Kind Of Science がオンライン公開された時の本家/.の記事 [slashdot.org]
コンタミは発見の母
Re:A New Kind of Science の邦訳はまだか… (スコア:0)
数学者などは二十歳で大成してしまうということなんでしょうね。
だから数学者の才能を開花させるには飛び級が非常に重要だと。
日本みたいに大学院まで行った頃には２０代後半だとすると、
既に数学者としては下り坂。
天才数学者にとって日本は地獄なんじゃないでしょうか。
Re:A New Kind of Science の邦訳はまだか… (スコア:0)
Wolfram Mathematicaって．．． (スコア:1, 参考になる)
この明らかな間違いは直した方が良いかと．．．
会社概要は「http://www.wolfram.co.jp/company/background.html [wolfram.co.jp]」で見られます．
Re:よくわからないのですが (スコア:0)