图灵最牛X的贡献是Universal Turing Machine啊

q
qama
楼主 (未名空间)

本民科念过Godel,邱奇,Turing的论文。
考证过年代。

我认为,Turing机是后于Godel和邱奇的计算模型的。
停机问题也没有优先权。

Turing之所以在CS有牛顿爱因斯坦的地位,
我认为是因为Universal Turing Machine。

可以跑程序的程序,这个脑洞大开的想法,就像闪电一样
让人震惊。这可能是人类有史以来最牛X的新鲜想法之一了。
没有这个,你怎么把不同的程序来比较呢?

即使在今日,lambda calculus据我所知也无法顺畅的
弄一个universal lambda machine达成一个合理的,好用的
计算理论。

我不知道CS科班出身的同学们怎么看。
这是我个人的结论。

另外本民科认为罗素的数学原理一书,就是现代OS,以及绑定各种
类库的雏形。

附录:

(1)
www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf

你看,Godel/Church这些数理逻辑神仙的脑子里,很明显没有
Universal Turing Machine

(2)
下面这段是Turing说的。
It is possible to invent a single machine which can be used to compute any
computable sequence. If this machine U is supplied with a tape on the
beginning of which is written the S.D ["standard description" of an action
table] of some computing machine M, then U will compute the same sequence as
M