アカウント名:
パスワード:
今回の結果によって、今のところ「最も単純な」万能チューリングマシンとなったのだそうです。
と、いうことのようですね。→「2つの状態と3つの色を持つ装置は(現時点で知られる限り最小の)万能チューリングマシンである」本家WIRED NEWS [wired.com]でもそのような表現になっています。 # それ以前では、「万能チューリングマシンを構成するためには、2つの状態と5つの色を持てば十分」という上限までが分かっていたようで。# (このときもWolfram氏は予想だけ) が、WIRED VISION日本語版の記事の表現だと、「最少の万能チューリングマシンは、2つの状態と3つの色を持てばよく、それ以下では成り立たない」ことが証明されたように読めてしまいますね。
普通のコンピュータのメモリ(や通常のチューリングマシンのテープ)と違うのは、縦方向と横方向の両方にメモリが無限大にのびているということです。
気になったのでちょっと賞のサイトで確認してきました.
読めば分かるんですが,横方向両側に無限というだけで縦方向は1マスしかないです.
わかりにくい記述ですが、要は、一回の動作でカウンタの位置のメモリを読み取り、縦に 1 進み、横に 1 か 0 か -1 進み、進んだ場所に決められた色を書き込むということです。
微妙に違います.
(a, b) -> (c, d, e)
という状態遷移関数に従った動作は以下です.
ステップの直前にヘッドがy番地にあるとします.y番地の色がaで内部状態がbだったとすると,y番地の色をcにして状態をdにしてヘッドをy+eに移動します.あとeは1か-1のみです.
移動してから色を塗るんじゃなくって,移動前に色を塗ります.
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
UNIXはただ死んだだけでなく、本当にひどい臭いを放ち始めている -- あるソフトウェアエンジニア
もう少し正確に言うと、 (スコア:4, 参考になる)
Wolframが提案したのは2つの状態と3つの色を持つチューリングマシンで、
今回の結果によって、今のところ「最も単純な」万能チューリングマシンとなったのだそうです。
Re:もう少し正確に言うと、 (スコア:4, 参考になる)
と、いうことのようですね。→「2つの状態と3つの色を持つ装置は(現時点で知られる限り最小の)万能チューリングマシンである」
本家WIRED NEWS [wired.com]でもそのような表現になっています。
# それ以前では、「万能チューリングマシンを構成するためには、2つの状態と5つの色を持てば十分」という上限までが分かっていたようで。
# (このときもWolfram氏は予想だけ)
が、WIRED VISION日本語版の記事の表現だと、「最少の万能チューリングマシンは、2つの状態と3つの色を持てばよく、それ以下では成り立たない」ことが証明されたように読めてしまいますね。
Re:もう少し正確に言うと、 (スコア:1)
状態が0と1として、色にあたるのって何なんでしょう?
それとも、色が0と1で、状態がメモリアドレスのようなものにあたる?
1を聞いて0を知れ!
Re:もう少し正確に言うと、 (スコア:3, 参考になる)
メモリ(テープ)に書き込む内容が色にあたります。3色あるので、1ビットに 0,1,2を書き込む、と考えることができます。
2が気持ち悪ければ、2ビットに 00,01,10 を書き込んでそれを1つのまとまり(セル)とみなしても構いません。
他に、現在どこのメモリを読んでいるかを表すプログラムカウンタのようなもの(ヘッド)があります。
普通のコンピュータのメモリ(や通常のチューリングマシンのテープ)と違うのは、
縦方向と横方向の両方にメモリが無限大にのびているということです。
さらに、可能な動作(プログラム
Re:もう少し正確に言うと、 (スコア:2, 参考になる)
気になったのでちょっと賞のサイトで確認してきました.
読めば分かるんですが,横方向両側に無限というだけで縦方向は1マスしかないです.
微妙に違います.
(a, b) -> (c, d, e)
という状態遷移関数に従った動作は以下です.
ステップの直前にヘッドがy番地にあるとします.y番地の色がaで内部状態がbだったとすると,y番地の色をcにして状態をdにしてヘッドをy+eに移動します.あとeは1か-1のみです.
移動してから色を塗るんじゃなくって,移動前に色を塗ります.
Re:もう少し正確に言うと、 (スコア:1)