※ [本文轉錄自 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 來說）是很不可思議的事情。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 78.109.182.40 -- 在細雨的午後 書頁裡悉哩哩地傳來 " 週期3 = ? " 然而我知道 當我正在日耳曼深處的黑森林 繼續發掘海森堡未曾做過的夢時 康德的諾言早已遠離......... 遠來的傳教士靜靜地看著山澗不斷反覆疊代自己的 過去 現在 和 未來 於是僅以 一顆量子渾沌 一本符號動力學 祝那發生在週一下午的新生 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.194.76.128