※ [本文转录自 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