※ [本文轉錄自 Math 看板 #1D5ynGje ]
作者: xcycl (XOO) 看板: Math
標題: Re: [其他] Stephen Wolfram 計算一切的理論 on Ted
時間: Mon Dec 27 07:14:20 2010
對 Cellular automata 不熟, 不過看得到的問題點挑一下 ...
※ 引述《CNSaya ( )》之銘言：
: ※ 引述《larsatic (OD)》之銘言：
: : 史蒂芬‧沃夫朗：計算一切的理論 | Video on TED.com
: : http://bit.ly/dNxX8Z
: : 在2分53秒的時候 Stephen Wolfram 特別把第30號規則拿出來討論
: : http://yfrog.com/h0njoij
: : http://yfrog.com/gzv18hoj
: : 並且還因此弄了一個 "A New Kind of Science"
: : http://www.wolframscience.com/nksonline/citation.html
: : 我想請問的是 在這麼多的規則中
: : 為何他對於第30號規則如此的興奮?
: : 有何特別之處嗎?
: 他用來示範的於影片中看起來應該是一種細胞自動機 (可以wiki it)
: 很奇妙的 這麼看似簡單的東西可以對應到 Universal Turing machine (也可以wiki it)
: 簡單講就是你改動它的基本規則 就可以讓它對應到所有可能的圖靈機
: 可以在wiki的 生命遊戲 頁面裡下載一個很簡單的版本來玩
: (但是 當然 它是二維的 而且似乎無法更動演化規則? 曾經花了幾天玩他)
: 然後他似乎是說某些規則演化的結果特別複雜 但還是有某種結構
: 他對這種規則有興趣 30號屬這一類
: 其實他是對所有的規則感興趣 同時特別地也對演化複雜度高的規則感興趣
: 因為所有的規則 就對應到所有的程式 所有的圖靈機
: 那圖靈機可以解決的問題 稱之為"可計算的"問題
: 那他又對什麼問題是可計算的感興趣
: 我只花了幾分鐘的時間看了他的書的網頁似乎也在談這些東西
: 感覺他好像圖靈的傳人阿! 對電腦計算有強大的狂熱
: 然後 有一個很有名的不可計算的問題叫做 Hilbert's tenth problem (wiki it)
: 然後 以上是由一個連Mathematica都不太會用的電腦與程式白癡唬爛的XD 隨便看看就好
Universal Turing machine (UTM) 跟 Turing machine (TM) 是不一樣的東西，
UTM 是能夠模擬所有 TM 的 TM。UTM 可以想做是編譯器或是直譯器，
而 TM 則是程式碼或程式。
而 TM 是可數無限多的，可計算問題其實就是能夠寫程式解決的問題，
或說存在演算法可以解決的問題。
Wolfram 在講的 Cellular automata (CA) 其實是
elementary CA (ECA), 下個狀態只由當前狀態跟兩個最靠近的點決定,
google 一下 Wolfram Mathworld 的定義就會看到圖片了。
每個狀態只有 0 跟 1 兩種可能, 從這邊我們可以推出 ECA 只有 256 種,
其中 rule 30 就是其中一種。
比較有趣的是, 其中 rule 110 是 Turing complete, 是一個 UTM。
其實 automata 可以看作一個動態系統, 這樣去會發現用這麼簡單的規則,
有些系統行為很單純, 有固定的 orbit 但像 rule 30 行為這麼複雜(chaotics)
（對 Wolfram 來說）是很不可思議的事情。