※ [本文转录自 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 来说）是很不可思议的事情。