t**********k
发帖数: 511 | 1 逻辑和计算机
从原理上说，计算机是一个无比简单的东西，就是一个逻辑处理器，计算机所做的所有
工作最后都是转化成逻辑运算来执行的。所以，任何能进行基本逻辑运算（非，与，和
）的东西，都可以用来构成计算机。计算机的构想早在在17世纪就提出来了，不过只能
用机械方式。
第一个真正现代意义上的计算机是用电子管实现的，但是它的应用非常有限，庞大，奇
贵，速度慢，而且耗能巨大。还有一个致命的缺陷，就是可靠性好不了。
现在的CPU集成了几亿只器件，如果用电子管，意味着上亿个插件，上十亿个焊点，这
样复杂的东西没有办法保证质量，更不可能大规模生产。计算机的发展赖于集成电路的
进步。
计算机的广泛应用，以至于完全改变了人类的生活，其硬件基础是上个世纪前30年以爱
因斯坦为首的那一拨人做的，有了量子物理和相对论，才能有凝聚态物理，才能有集成
电路，接下来才可能有计算机，网络的广泛使用。
记得曾经在网上有人讨论爱因斯坦和爱迪生哪一个更牛，这实在有点过分，两个人完全
不在一个档次，而且差得很远。爱因斯坦是一个科学家，《维基百科》说也... 阅读全帖 |
|
g*****l
发帖数: 424 | 2 前言：
今天，图灵百年庆典在伯克利中央街2050号举行。此文受此启发，为非正式文
，仅供参考。
本文写在计算机之父Alan Turing （阿兰·图灵）诞辰一百年，希望天堂的图
灵知道世界并没有他离去的时候所想象的那样孤独和凄凉。
by 灵致
Another version with pics and music is available at:
http://user.qzone.qq.com/176497662/blog/1346827666
一百年前的六月二十三号，英国伦敦，在众多这天诞生的婴儿中，有一个不起眼的小男
孩被命名为阿兰·图灵（Alan Turing）。
身为孩子父亲的朱利斯·麦席森·图灵（Julius Mathison Turing）在喜悦之余，并没
有意识到自己的儿子在不久的将来，会给后世留下无穷启发，并且其发明开启了一场改
变全人类生活的信息革命。这个发明，叫计算机。
可以说，计算机的发明，实际上并非只有图灵的功劳。在此之前的先辈们所作的诸多努
力无疑也为这个发明奠定了时间和可能性的基... 阅读全帖 |
|
s******y
发帖数: 28562 | 3 哎，你真的自己去看了你贴的那三篇文章了么？
我至少认真的看了第三篇，里面说的根本就不是你说的那些东西。
(3) Why did computer science make a hero out of Turing?
Maarten Bullynck, Edgar G. Daylight, Liesbeth De Mol
Communications of the ACM
Volume 58 Issue 3, March 2015
Pages 37-39
至于说什么Enigma，问题就出在这里：正经的计算机学界根本就没有人声称过图灵在里
面有多大贡献。所以王垠的这个攻击根本就莫名其妙。
而你举例说的那些什么没有任何实际应用上的机器是用图灵机原理做的，这个本来就是
常识，也从来没有计算机学界的人说图灵机适合直接用来制作一个机器，所以有什么好
争议的？所以这个也是属于无中生有的争论。就是把本来不是话题的东西炒成话题。至
于你非要说好莱坞的人怎么怎么说，拜托，我们需要把自己降低到那个档次去说话么？
除非王垠他也许可能觉得自己是一个娱乐明星，所以他需要就好莱坞编的故事去争论。
至于说Lam... 阅读全帖 |
|
g*****l
发帖数: 424 | 4 前言：
今天，图灵百年庆典在伯克利中央街2050号举行。此文受此启发，为非正式文
，仅供参考。
本文写在计算机之父Alan Turing （阿兰·图灵）诞辰一百年，希望天堂的图
灵知道世界并没有他离去的时候所想象的那样孤独和凄凉。
by 灵致
Another version with pics and music is available at:
http://user.qzone.qq.com/176497662/blog/1346827666
一百年前的六月二十三号，英国伦敦，在众多这天诞生的婴儿中，有一个不起眼的小男
孩被命名为阿兰·图灵（Alan Turing）。
身为孩子父亲的朱利斯·麦席森·图灵（Julius Mathison Turing）在喜悦之余，并没
有意识到自己的儿子在不久的将来，会给后世留下无穷启发，并且其发明开启了一场改
变全人类生活的信息革命。这个发明，叫计算机。
可以说，计算机的发明，实际上并非只有图灵的功劳。在此之前的先辈们所作的诸多努
力无疑也为这个发明奠定了时间和可能性的基... 阅读全帖 |
|
g*****l
发帖数: 424 | 5 前言：
今天，图灵百年庆典在伯克利中央街2050号举行。此文受此启发，为非正式文
，仅供参考。
本文写在计算机之父Alan Turing （阿兰·图灵）诞辰一百年，希望天堂的图
灵知道世界并没有他离去的时候所想象的那样孤独和凄凉。
by 灵致
Another version with pics and music is available at:
http://user.qzone.qq.com/176497662/blog/1346827666
一百年前的六月二十三号，英国伦敦，在众多这天诞生的婴儿中，有一个不起眼的小男
孩被命名为阿兰·图灵（Alan Turing）。
身为孩子父亲的朱利斯·麦席森·图灵（Julius Mathison Turing）在喜悦之余，并没
有意识到自己的儿子在不久的将来，会给后世留下无穷启发，并且其发明开启了一场改
变全人类生活的信息革命。这个发明，叫计算机。
可以说，计算机的发明，实际上并非只有图灵的功劳。在此之前的先辈们所作的诸多努
力无疑也为这个发明奠定了时间和可能性的基... 阅读全帖 |
|
l**n
发帖数: 7272 | 6 【 以下文字转载自 WaterWorld 讨论区 】
发信人: greatel (灵致), 信区: WaterWorld
标 题: 【原创】 图灵百年：一世孤独成全百年辉煌
发信站: BBS 未名空间站 (Wed Sep 5 14:35:16 2012, 美东)
前言：
今天，图灵百年庆典在伯克利中央街2050号举行。此文受此启发，为非正式文
，仅供参考。
本文写在计算机之父Alan Turing （阿兰·图灵）诞辰一百年，希望天堂的图
灵知道世界并没有他离去的时候所想象的那样孤独和凄凉。
by 灵致
Another version with pics and music is available at:
http://user.qzone.qq.com/176497662/blog/1346827666
一百年前的六月二十三号，英国伦敦，在众多这天诞生的婴儿中，有一个不起眼的小男
孩被命名为阿兰·图灵（Alan Turing）。
身为孩子父亲的朱利斯·麦席森·图灵（Julius Mathison Tur... 阅读全帖 |
|
g*****l
发帖数: 424 | 7 前言：
今天，图灵百年庆典在伯克利中央街2050号举行。此文受此启发，为非正式文
，仅供参考。
本文写在计算机之父Alan Turing （阿兰·图灵）诞辰一百年，希望天堂的图
灵知道世界并没有他离去的时候所想象的那样孤独和凄凉。
by 灵致
Another version with pics and music is available at:
http://user.qzone.qq.com/176497662/blog/1346827666
一百年前的六月二十三号，英国伦敦，在众多这天诞生的婴儿中，有一个不起眼的小男
孩被命名为阿兰·图灵（Alan Turing）。
身为孩子父亲的朱利斯·麦席森·图灵（Julius Mathison Turing）在喜悦之余，并没
有意识到自己的儿子在不久的将来，会给后世留下无穷启发，并且其发明开启了一场改
变全人类生活的信息革命。这个发明，叫计算机。
可以说，计算机的发明，实际上并非只有图灵的功劳。在此之前的先辈们所作的诸多努
力无疑也为这个发明奠定了时间和可能性的基... 阅读全帖 |
|
G***l
发帖数: 355 | 8 只是另外一种方式，就像牛肉和猪肉没有哪个更好吃一样。
实在不想搞语言坑。这个算是“科普”文吧。fp并不是跟oo对立的，跟什么
declarative，dynamic，script等等更没有一毛钱直接关系。fp说到底就是对lambda
calculus，另外一种可图灵机等价的可计算方式的支持。
lambda calculus和图灵机，也不是哪个更先进。大多程序都是实现各种算法和业务逻
辑。有一些算法和逻辑，用图灵机的方式实现更顺手。而又有不少算法和业务逻辑，如
果能用lambda calculus的方式实现会比传统的状态机好，更易实现，易读，易修改，
不易出错。在那些情况下，fp就能发挥优势。哪怕是C#,Ruby这样非fp的语言，里面加
入了一些简单的fp的支持，都大受欢迎，也说明了这一点。fp以前不流行主要是计算机
硬件是图灵机的方式，于是底层的语言也是图灵机方式，后来渐渐发展流行起来的语言
自然也是图灵机方式。如果计算机程序的应用范围还停留在90年代以前，那现在也不会
有fp的屁事。主要是因为计算机程序渗透到各个领域，越来越多的复杂算法和业务逻辑
的实现和维护的挑战，让人们体会了im... 阅读全帖 |
|
l******t
发帖数: 55733 | 9 你说的这些很对。有时也需要退一步换对方视角看看。
是的图灵机本身完备。现在也并没有lambda机而是转换为图灵机也反证图灵机是完备的。
图灵机缺的是没有抽象和应用的过程。而抽象和应用这是lambda的内质。理论上lambda
式可以自动机器演算判定，编程上FP的代码实现也是高度抽象高度精简比图灵机指令式
表达有效的多。
OO的问题并不是图灵机的的问题而是本身的问题。基础描述不清基本等同口头描述。
Corner case修修补补添加各种轮和地心轮说可以媲美。
算法，代码，语言，feature都可以有好有坏。语言也有high level low level的。目
测fp应该是下一个level。现在的趋势也是各种语言纷纷marry 基本lambda。FP本身并
没有很多feature，lambda，trait，强类型自动推，pattern match，lazy，加几套基
本库，差不多够了吧。scala是被OO兼容搞坏了。
先进也要等主流。太超前的下场就是被烧死。感觉现在主流已经很靠拢。haskell轮子
不够scala还是过渡，java马上20年了已经很长寿了。现在就等一个和c cpp ja... 阅读全帖 |
|
T********i
发帖数: 2416 | 10 昨天还和聊这个问题。RNN能模拟图灵机是90年代中期证明了的。不知道为啥花了这么
多年才火起来？
这个模拟图灵机是无限逼近。机理完全不同。图灵机内存是无限的。RNN模拟的代价是
什么？如何估计？这方面有论文么？是不是最后陷入堆机器的邪路？
据说谷歌的神经图灵机，只完成一项简单任务，拷贝字符串。
话说回来，真模拟成了又如何？假定模拟出一个完美大脑，样样都比人强。而且没有神
经病。用来干啥？搞不好还要训练它成一个程序员来写图灵机程序。。。 |
|
n*********2
发帖数: 357 | 11 > 用存储在介质上的程序来控制机器这个概念自古就有。
> 即使没有Church没有Turing，计算机一样会被造出来的
就象你说的， 基于存储程序的计算机与图灵没有什么关系。 有没有图灵，基于存储程
序的计算机都会被造出来（现在的一种说法是这一概念是John von Neumann 在和John
Mauchly， J. Presper Eckert讨论时总结出来的）。有了存储程序的计算机， 时间
复杂度和空间复杂度的概念就会相对自然的出来。 所以计算复杂度 这个分支也不应当
归功到图灵的头上。
图灵的主要贡献是抓住了计算的本质： 什么是计算？ 什么东西是可计算的？什么东西
是不可计算的？很怪异的是，这些问题可以用一个很看似简单的机器（图灵机）表现出
来。
> 沿着图灵机走才能走出来计算机科学 和现在的IT业。
但是图灵机这个东东跟现在的IT业还是有很大的距离的。 没有图灵机， IT 业也照样
会出来。 当然， 你可以争辩说，没有图灵机，这个行业的基础不牢固。 |
|
g*****l
发帖数: 424 | 12 前言：
今天，图灵百年庆典在伯克利中央街2050号举行。此文受此启发，为非正式文
，仅供参考。
本文写在计算机之父Alan Turing （阿兰·图灵）诞辰一百年，希望天堂的图
灵知道世界并没有他离去的时候所想象的那样孤独和凄凉。
by 灵致
Another version with pics and music is available at:
http://user.qzone.qq.com/176497662/blog/1346827666
一百年前的六月二十三号，英国伦敦，在众多这天诞生的婴儿中，有一个不起眼的小男
孩被命名为阿兰·图灵（Alan Turing）。
身为孩子父亲的朱利斯·麦席森·图灵（Julius Mathison Turing）在喜悦之余，并没
有意识到自己的儿子在不久的将来，会给后世留下无穷启发，并且其发明开启了一场改
变全人类生活的信息革命。这个发明，叫计算机。
可以说，计算机的发明，实际上并非只有图灵的功劳。在此之前的先辈们所作的诸多努
力无疑也为这个发明奠定了时间和可能性的基... 阅读全帖 |
|
a****y
发帖数: 1035 | 13 【 以下文字转载自 USTC 讨论区 】
发信人: greatel (灵致), 信区: USTC
标 题: 【原创】 图灵百年：一世孤独成全百年辉煌
发信站: BBS 未名空间站 (Wed Sep 5 14:35:30 2012, 美东)
前言：
今天，图灵百年庆典在伯克利中央街2050号举行。此文受此启发，为非正式文
，仅供参考。
本文写在计算机之父Alan Turing （阿兰·图灵）诞辰一百年，希望天堂的图
灵知道世界并没有他离去的时候所想象的那样孤独和凄凉。
by 灵致
Another version with pics and music is available at:
http://user.qzone.qq.com/176497662/blog/1346827666
一百年前的六月二十三号，英国伦敦，在众多这天诞生的婴儿中，有一个不起眼的小男
孩被命名为阿兰·图灵（Alan Turing）。
身为孩子父亲的朱利斯·麦席森·图灵（Julius Mathison Turing）在喜悦之余，并没... 阅读全帖 |
|
P**********e
发帖数: 2964 | 14 图灵很伟大。
【 以下文字转载自 USTC 讨论区 】
发信人: greatel (灵致), 信区: USTC
标 题: 【原创】 图灵百年：一世孤独成全百年辉煌
发信站: BBS 未名空间站 (Wed Sep 5 14:35:30 2012, 美东)
前言：
今天，图灵百年庆典在伯克利中央街2050号举行。此文受此启发，为非正式文
，仅供参考。
本文写在计算机之父Alan Turing （阿兰·图灵）诞辰一百年，希望天堂的图
灵知道世界并没有他离去的时候所想象的那样孤独和凄凉。
by 灵致
Another version with pics and music is available at:
http://user.qzone.qq.com/176497662/blog/1346827666
一百年前的六月二十三号，英国伦敦，在众多这天诞生的婴儿中，有一个不起眼的小男
孩被命名为阿兰·图灵（Alan Turing）。
身为孩子父亲的朱利斯·麦席森·图灵（Julius Mathison Turing）... 阅读全帖 |
|
n**********5
发帖数: 1707 | 15 花了一天看了150多章的《重生之超级战舰》，故事是很能编。但是还是《三体》好。
《三体》里面的降维攻击很有创意很有共鸣。
去年年底到今年年初开始，我的脑袋好像突然睡醒。感觉就是第二个春天，20多岁之后
就再也没有这么活跃过。时常冒出许多古怪的念头。如“多维”图灵机就和《三体》里
的高维文明很有共鸣。如果时间不是问题，图灵机理论有何影响。如图灵机以光速运行
会如何；图灵机在黑洞里面运行回如何。图灵机是基于整数的。如果有基于实数的图灵
机会如何。等等等等。
所以说《三体》能获奖，绝不是因为抄袭了别人的文明分级等内容，而是它真的有不少
原创性的点子。不过作者自己不是这些方面的专家，能想出这些东西已经相当不错了。 |
|
n**********5
发帖数: 1707 | 16 你把危机百科里的图灵机，可计算性，计算复杂性等东西看懂，看不懂背下来。特别是
NP是啥千万别搞错。最好用高级语言写一个图灵机。麻婆interview的时候就跑不掉了
。被问到不懂或百科里没提过的部份千万别脸红，就说这个问题你还在想。99%的码公
不懂图灵机。如果你能把对角线法弄懂，已经秒杀99.9%的码公了，名笑博士都大半被
你斩于马下。如果你还能说出康托尔、哥德尔的大名，深情回忆康托尔如何撩开上帝的
面纱最终死在精神病院，这辈子你软饭就有着落了。大叔我上知天文下懂地理，古今中
外，全没用上。就凭图灵机就够用了。 |
|
n********g
发帖数: 6504 | 17 其实是两个层次，问题的集合的集合。
某图灵机接收的语言={问题或输入 | 被某图灵机接收}
（语言）类={语言 | 类定义}
P、NP都是语言类。
举例说，有一台图灵机会排序，则所有可能的输入串（问题）构成这台图灵机所能接收
的语言。另一个图灵机会找到输入串中最大/最小/平均数。这些图灵机接收的语言是P
的子集，都属于P这个类。当然也属于NP。P是特殊的NP。 |
|
k*****e
发帖数: 22013 | 18 www.google.com
纪念图灵，google主页图标变成了一个图灵机的游戏。
这个游戏太好玩了。非常形象地演示了图灵机的原理。
每过一关，Google这6个字母就会点亮一个，点亮6个字母通关。
纸带上有一个初始状态，右上角方框是目标状态，
你必须在底下的运算规则里面修改，使初始状态经过运算会等于目标状态。
(来自wiki)
图灵构造出一台假想的机器，该机器由以下几个部分组成：
1.一条无限长的纸带TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来
自有限字母表的符号，字母表中有一个特殊的符号表示空白。纸带上的格子从左到右依
次被编号为0, 1, 2, ...，纸带的右端可以无限伸展。
2.一个读写头HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符
号，并能改变当前格子上的符号。
3.一套控制规则TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符
号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。
4.一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目
是有限的，并且有一个特殊的状态，... 阅读全帖 |
|
t****a
发帖数: 1212 | 19 这是多年前的一篇牛文。一家之言，仅供参考。
通天塔导游
(译注：圣经记载：在远古的时候，人类都使用一种语言，全世界的人决定一起造一座
通天的塔，就是巴别塔，后来被上帝知道了，上帝就让人们使用不同的语言，这个塔就
没能造起来。 巴别塔不建自毁，与其说上帝的分化将人类的语言复杂化，不如说是人
类自身心灵和谐不再的分崩离析。之所以后来有了翻译，不仅是为了加强人类之间的交
流，更寄达了一种愿望，希望能以此消除人际的隔阂，获求来自心灵的和谐及慰藉。真
正的译者，把握血脉，抚平创痕，通传天籁，开启心门。)
这是我写的旋风式的编程语言简介—我本来为亚马逊开发者杂志本月的期刊写的，但是
发现我写的东西没法…见人。
首先，我偶尔一不小心口出脏话，或者对上帝不恭的话，所以对很官方很正式的亚马逊
上发表是不合适的; 所以我就把它塞到我的博客里了，我的博客反正没人看的。除了你
以外。是的，只有你会看，你好啊。
其次，这是一项进行中的工程，现在只是东打一耙西搞一下，还没有精加工过的。又一
个把它写到博客里的很大的理由。不需要很好，或很完整。就是我今天想说的一些话。
请随便！
我的旋风式简介会讲C，C++，Lis... 阅读全帖 |
|
h*****m
发帖数: 1034 | 20 我这正回复着呢，你咋就跑了呢？幸好我拷贝了。真心求教。
多谢答疑。再给民科讲讲图灵机和非图灵机的差别呗。: )
非逻辑行为是不是非图灵机特有的？图灵机能不能百分之百完全模拟非图灵机？
百分之百民科问题，问得不好请随便笑话。: )
你要是不高兴，我把这贴删掉。。。
AlphaGo |
|
s******y
发帖数: 28562 | 21 至于你说的这一点：
“d.王垠没有指出（或者不愿看到）的是，Universal 图灵机的确指出了（通用）计算
的本质。 这是图灵厉害的地方。但是图灵这个贡献在很长的时间都没有被人认识到。”
这个我完全同意。这个也是为什么图灵在计算机学理论里面有如此地位的关键原因。
但是王垠没有指出这一点，说明他根本就不知道图灵机对于计算机科学有什么意义。
所以这个是为什么我说他连半桶水都不如。
其实我又想了一下，你和我对于绝大部分要点的看法都是一样的，但是我们之间的主要
分歧在于我的评论着重点在于王垠，而你的评论着重点在于图灵。
我其实并不认为图灵有多么的牛X闪闪，但是我觉得王垠对图灵的评价完全是本末倒置
。你看他写的那个原文里，先是说图灵机不如Lambda 容易理解，然后又说图灵对
ENIGMA 项目贡献不大，然后又说图灵根本不是发明计算机的人。但是，这些事情本来
就是整个计算机科学领域的人都知道的事情，也不知道有什么值得让他来洋洋洒洒的写
这么一大片恍然大悟文。尤其是他还得意洋洋的说他查了如何如何多的文献才得出这些
个结论，让人听了感觉就是，某个人跑到大街高声叫嚷说他用了几十年的心血，用了多
种高... 阅读全帖 |
|
wy
发帖数: 14511 | 22 先来一点补充：
Church's Thesis: 所有通用计算机可以解决的问题，图灵机都
可以解决，换句话说就是图灵机的计算能力和通用计算机完全一样，
不多也不少。所以我们才可以使用图灵机解决以下问题：可计算性与
计算复杂性。
可计算性就是说，什么问题是计算机可以解决的，而什么问题是不可以的。
计算复杂性就是说，对于可以解决的问题，我们可以以什么样的成本去解决。
计算复杂性的问题，首先说一下为什么计算机科学家认为NP问题
对于决定性机器而言其产生的障碍是本质的。
举个例子，如果我们假定n=1时为了解决问题，计算机需要执行1条指令，
在假设每条指令执行时间等长，那么n=2时，对于一个NP问题，计算机需要
执行2条指令...那么n=n1时，计算机就需要执行2^(n-1)条指令，现在
我们就算有一台无比强大的机器，他的速度达到2^10000指令/秒，可是，
如果这时候n=100000,他的执行时间仍然达到2^90000秒！大家可以试试，
如果一个多项式时间的算法，情况如何。
计算复杂性问题可以通过量子计算机（非决定性图灵机）得到缓解，但是
不是解决！因为除了NP class,还存在有成本更高 |
|
d*q
发帖数: 4 | 23 整个中科院的人讲的东西给你看看
王小云的水平就不说了
从专业角度说一下应明生，我很佩服的一个人
本帖最后由 eher 于 2010-12-26 07:36 编辑
虽然我不完全是他那个领域的，不过他的工作我还是了解一点。最近科学院的同事们越
来越多提起他，就在网上搜了一些他的介绍，汇总与下，他是我真正佩服的少数中国科
学家之一。
可以说，在姚期智回归中国之前，应明生是事实上的中国理论计算机第一人，是真正做
研究的人，国内极少有人能达到他的境界。国内确实有不少老院士，但是，能跟的上甚
至引领国际潮流的只有应明生一个人。最难得的是，此人出身于一个不知名的师范学校
，然后清华慧眼识珠请他过去，他在清华也做出了一系列极为瞩目的成绩，他的学生，
如张胜誉去了香港中文大学任助理教授，冯沅和段润尧成了澳洲科技大学的副教授等等。
他早期做概率程序与进程方面的研究，并因此拿了“王选奖”，国外同行的评价是“
beyond what we have seen so far”，“really novel ideas”,“a new angle, …
which other researchers in this... 阅读全帖 |
|
L*****e
发帖数: 8347 | 24 很早就想写这样一篇博文了，可是一直没来得及动笔。在学校的时候，时间似乎总是不
够用，因为一旦有点时间，你就想是不是该用来多看点论文。所以我很高兴，工作的生
活给了我真正自由的时间，让我可以多分享一些自己的经验。
我今天想开始写这系列文章的原因是，很多程序员的头脑中都有一些通过“非理性”方
式得到的错误观点。这些观点如此之深，以至于你没法跟他们讲清楚。即使讲清楚了，
一般来说也很难改变他们的习惯。
程序员的世界，是一个“以傲服人”的世界，而不是一个理性的，“以德服人”的世界
。很多人喜欢在程序里耍一些“小聪明”，以显示自己的与众不同。由于这些人的名气
和威望，人们对这些小聪明往往不加思索的吸收，以至于不知不觉学会了很多表面上聪
明，其实导致不必要麻烦的思想，根深蒂固，难以去除。接着，他们又通过自己的“傲
气”，把这些错误的思想传播给下一代的程序员，从而导致恶性循环。人们总是说“聪
明反被聪明误”，程序员的世界里，为这样的“小聪明”所栽的根头，可真是数不胜数
。以至于直到今天，我们仍然在疲于弥补前人所犯下的错误。
所以从今天开始，我打算陆续把自己对这些“小聪明”的看法记录在这里，希望看了的... 阅读全帖 |
|
d*******r
发帖数: 3299 | 25 图灵机和美国工程师把计算机搞出来，貌似是没有直接关系的
说实话，图灵机对大家理解计算机模型真的很有帮助吗? 还是只是理论派们玩具？
我虽然计算理论的课是A+, 但是每次过一段时间，我就看不懂，写不出那些证明了，忘
光光了。
王同学也在他的blog里面说过这问题，不过他推崇的是 lambda 那一套，那一套确实是
先有理论，再有产品的 (Lisp).
他说那一套我不懂，但是每次有小师弟问我图灵机怎么用来理解计算机，我都会说：
图灵机那个过度简化的模型不是很好用，你需要大概去看看体系结构的入门课，理解简
化版的 CPU 指令集, 寄存器，memory/硬盘就是一个长长的一维数组，程序执行，就是
CPU 在寄存器和这个一维数组上改变状态就是。这个模型是比图灵机和它那一堆经典
推论和证明更好懂的模型。 |
|
g****t
发帖数: 31659 | 26 你进去的随机数是有限长的。
例如你的程序有个地方是随机数0或者1。
这相当于你一次写了2个程序。这
这没什么本质区别。和你是不是知道0或者1也没关系。
你怎么使用这两个程序的结果是另一回事。
但包含随机数截断输入的程序就是多个确定性图灵机的集合。
: 你看一下确定性图灵机的定义，要求每一步都确定的。
: 如果做不到就不是确定图灵机了，这个在数理逻辑里面很重要啊。30年前
已经知
道AI通
: 过确定图灵机实现难度不弱于NPC问题，所以当时的AI才迅速进入寒冬期
，除了
日本政
: 府不学无术的官员上当，别人都不正经投钱了。
|
|
R****2
发帖数: 342 | 27 时间反演可以这样理解，出于安全考虑matrix的设计就是内部不能影响到外部的世界。
所以不可能由matrix内部触发外部的时间箭头变化。当外部箭头不变时，由于存储限制
，不能模拟反演。当外部箭头变化时，由于matrix状态整个跟着回去了，matrix内部无
法感知到时间的变化。
粒子束干涉原理很简单，当粒子打上屏幕的时候由于速度需要提高精度导致位置精度下
降，所以需要根据一定的计算方法产生扩散。至于为什么会以波的形式表现是由于薛定
谔方程的解是波的形式。matrix之所以这样设计，我估计是为了方便FFT变换到频域之
后进行运算！否则弄个均匀分布什么的搞个狄拉克函数不方便matrix算啊。
matrix对世界的解释是相当完整的。现在该理论唯一的问题就是如何验证。我考虑是往
图灵机的方向走，看看matrix中的什么现象可以表现图灵机的限制从而证明matrix是个
图灵机 |
|
P***y
发帖数: 2885 | 28 这个要顶。当年俺就是提了一下哥德尔和图灵机。
：你把危机百科里的图灵机，可计算性，计算复杂性等东西看懂，看不懂背下来。特别
是NP是啥千万别搞错。最好用高级语言写一个图灵机。麻婆interview的时候就跑不掉了
：。被问到不懂或百科里没提过的部份千万别脸红，就说这个问题你还在想。99%的码公 |
|
n**********5
发帖数: 1707 | 29 你面对的问题是阿列夫零无穷，比你的氢原子总数的总数次方次方次方下去都要多。
这个问题其实并不难解。问题是考试100分容易，真正知道可数无穷的人少，知道图灵
机的人更少，同时知道两者的人更少。我bet库克并不是很本质地认识可数无穷或图灵
机。他是研究代数出身的。所以他能定义出NP难问题。但是没能证明P其实等于NP。库
克的课程太枯燥，没有什么学生愿意选，不想拖累GPA。学什么都对找工作有帮助。学
代数真是脑子坏了。因此也决定了P＝NP问题令人生畏。但其实并不特别复杂。
我相信这个问题不久就会有突破。
图灵机是建立在可数的基础上的。通用图灵机对应阿列夫零。但是量子系统不是可数的
。这也是“测不准”的根源。哪怕最简单的量子系统，计算能力都要强于通用图灵机。
令人感兴趣的是这些基数是没有上限的。量子系统对应实数域。之上的层次的物理意义
是什么。令人好奇。也许是人类还没有观察到的物理现象。
时) |
|
|
n**********5
发帖数: 1707 | 31 薛定谔猫的生死需要测量/观察才能知道。而测量和观察破坏了猫的状态，猫只剩下生/
死两种状态之一。思维误区是为什么测量如此重要。
在计算机科学中，测量就是一种计算。这种计算可以用代数函数方式表示（丘奇），如
y=f(x)；也可以用几何图灵机方式表示（图灵）；还可以用门电路表示（苏联）。但总
归要计算。作为一种计算（从一个状态推理将来状态的过程），图灵（机）的贡献是不
存在一个方法/上帝（图灵机）能够不经过计算就知道任意f对输入x的结果y。也就是说
，即使你设计一系统已知猫的生死就是50/50，对具体的一个实例（输入），如果你不
计算，你就不知道结果究竟是生还是死。这就是观察的意义。
哪么测量为什么会破坏系统的状态。很简单，计算过程中图灵机要修改磁带记录中间结
果。不破坏状态的测量是不存在的。只不过有些计算（测量）/图灵机/算法修改等少，
有些多。除非输入即结果。所以观察结果不影响结果。
由于观察是计算。计算就有步骤。这个步骤就定义了测量或者说物质能量相互作用的过
程不可能无穷快。这个最短时间就表现为这个宇宙的极限速度。
时间之箭通常的物理学解释是熵增。但是很多人会不服气怎么能从一封闭系统... 阅读全帖 |
|
n**********5
发帖数: 1707 | 32 发明这个量子算法的是一位天才。不过没有人知道怎么实现、能否实现。
正如超光速时空旅行是可能的，但如果人不能活着看到有什么意义。在计算机科学里，
图灵机就是光速。在图灵教里任何超越图灵机都是不可能的。上帝也不能超越图灵机。
在我看来，获得解的叠加态（叠加成千上万的量子）很难但可能。最难的是这个瞎碰测
波长、频率的过程会不会永不停机。如果可能永不停机。则和概率方法求近似最优解的
思想没有什么区别。
分钟 |
|
发帖数: 1 | 33 歪了那么久的楼。说说计算机如何进行推理。
康托尔：定义了数；罗素：一切东西都可以用一个（整）数表示；图灵：定义了通用机
器算这些数
你可以把一个（图灵机的）排列组合用一个整数表示出来。图灵机每算一步，数变了，
就等价于一步推理。整个推理过程就是迭代的过程。图灵的老师邱奇用函数计算表达这
一（推理）过程。北大版讨论可计算性时也是用函数的方式。是我读到的唯一用函数方
式讨论此问题的。怕是哪作者死了就所有人都用图灵机了。
这个数，也就是code。构造这个数的过程就是coding。构造一个机器对应的数的过程是
一种特殊的coding，用人话说就是编程。大多数CS在干的就是在不同的层次编程。有了
code，就可以在通用机器上跑模拟特定的机器得出计算结果。
1+1是计算，计算不限于1+1。不要把一帮学应用数学出身搞出来的东西代表CS。这些人
怕是计算是什么都不知道。“计算”可以解释薛定谔猫。压根就不需要引入什么智慧生
物。物理上的“观察”就是一种计算。照相机、底片就是程序。人的观察就是计算。如
果不计算，你不知道计算结果（图灵的不可计算性，没有办法不经过实际的计算得知计
算结果）。
你说计算机不能... 阅读全帖 |
|
发帖数: 1 | 34 歪了那么久的楼。说说计算机如何进行推理。
康托尔：定义了数；罗素：一切东西都可以用一个（整）数表示；图灵：定义了通用机
器算这些数
你可以把一个（图灵机的）排列组合用一个整数表示出来。图灵机每算一步，数变了，
就等价于一步推理。整个推理过程就是迭代的过程。图灵的老师邱奇用函数计算表达这
一（推理）过程。北大版讨论可计算性时也是用函数的方式。是我读到的唯一用函数方
式讨论此问题的。怕是哪作者死了就所有人都用图灵机了。
这个数，也就是code。构造这个数的过程就是coding。构造一个机器对应的数的过程是
一种特殊的coding，用人话说就是编程。大多数CS在干的就是在不同的层次编程。有了
code，就可以在通用机器上跑模拟特定的机器得出计算结果。
1+1是计算，计算不限于1+1。不要把一帮学应用数学出身搞出来的东西代表CS。这些人
怕是计算是什么都不知道。“计算”可以解释薛定谔猫。压根就不需要引入什么智慧生
物。物理上的“观察”就是一种计算。照相机、底片就是程序。人的观察就是计算。如
果不计算，你不知道计算结果（图灵的不可计算性，没有办法不经过实际的计算得知计
算结果）。
你说计算机不能... 阅读全帖 |
|
m***a
发帖数: 2262 | 35 不是王垠。王浩，金岳霖的学生，哥德尔晚年的知己。提出的Wang Tiles，和图灵机等
价的形式系统。其实和图灵机等价的自动机或形式系统很多，关键是其直接物理映射或
较为直接的物理映射的可应用程度。图灵机不光早，在这方面也有优势。 |
|
发帖数: 1 | 36 你也可以想想为啥近代以来CS理论家大多同时是“理论物理学家”。量子计算的数学基
础是什么？能否成为我说的通向比实数域更高一层的大门？CS里的“计算”和物理中的
“测量/观察”本质上就没有区别。
如薛定谔的猫在CS中简单得不能再简单。整个密室就是一程序/图灵机。你根据经验知
道输出是0/1的概率50/50（或其它比例）。问题是不存在一个不运行程序而能够预知结
果的方法（图灵机）。这是图灵的一大贡献以及为何图灵机成为标准模型。所以不运行
程序/观察，永远不知道猫是死是活。
码工用的数学是这么多学科中最现代化的。 |
|
n********g
发帖数: 6504 | 37 方励之在这点上是正确的。熵这个概念很重要。也能揭示图灵机为何有如此神奇的力量
。图灵机其实本质上就是热机。或者热机本质上就是图灵机。这一点我可能生命不够要
留给下一代继续研究。版权所有，引用记得列明出处。。 |
|
W******g
发帖数: 887 | 38 图灵机！图灵机！
博士们一定要努力进制造图灵机的公司！ |
|
s******c
发帖数: 1920 | 39 查了一下 用来定义np的非确定性图灵机和量子图灵机还不是一回事儿。np难问题是否
能在多项式时间内被量子图灵机解决依然未知。 |
|
t***t
发帖数: 6066 | 40 超越图灵机，想都不要想。现在大家就是想能否让它快点。
NP问题里那个非确定性图灵机也还是图灵机。 |
|
a*****s
发帖数: 1121 | 41 good point.
但是说俺全答错，有点绝对了。不过无所谓，探讨问题吗，闻者足戒。
region 如果是在map上的话，在相对一段时间内是固定的，可以从某个table上根据划
分查出来的。
用spark-streaming只要读个database的RDD就是了。
瓶颈在系统设计里面永远是个相对概念，是相对于你的上层用户，下层系统，和实际
SLA来说的。如果你用MapReduce解决不了，latency太长，那么瓶颈在这里，换其他计
算平台，实在不行你可以自己写MPI代码。所有“瓶颈”无非是两个方面，时间和空间
，因为图灵机就是一个读写头和纸带。所有系统都是图灵机的实现。
扯再多都是如何根据具体问题优化你当前的图灵机。
好的设计是你能通过对机器来满足你的SLA，你懂得越低层，你的power就越大，实在不
行咱不用现在主流设计，从头来自己搞一套，当然money driven的公司是绝对不允许你
这么干的。解决近期问题就行。不care你用啥。 |
|
S***k
发帖数: 370 | 42 似乎是 OO language 同 functional language 的差别.那么在C# 这个OO 里引进
functional programming (Linq) 应该怎样看?
这其实就是编码，在我们现在看来是很显然的，因为一个程序就可以被编码成二进制数
，反过来也可以解码。但是在当时这是一个全新的思想，也是最关键的辅助性工作之一
，另一方面，这正是“程序即数据”的最初想法。以此为前提开放了计算机界最初的两
朵奇葩：一个就是图灵机，另一个是lambda算子。图灵机着重于运算的机械过程（可能
是受小白这个机械系学生的影响^_^)，lambda算子着重于运算的抽象性质。这两朵奇葩
后来又结出了不同类型的程序语言，图灵机的后代是C,C++,Java等等，lambda算子的后
代是Lisp,Scheme,Haskell等等。这些是后话了。 |
|
t******n
发帖数: 2939 | 43 ☆─────────────────────────────────────☆
l63 (l63) 于 (Thu May 23 00:34:22 2013, 美东) 提到:
假设素数只有有限个, 记为 p_1,p_2,...,p_k
考察 N = p_1*p_2*...*p_k + 1
可知: 对于任意i = 1,2,3,...,k, p_i 不能整除 N
由素数的定义:
a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除
可知: N是素数
这与素数只有p_1,p_2,...,p_k矛盾.
故假设不成立.
所以素数有无穷多个.
☆─────────────────────────────────────☆
l63 (l63) 于 (Thu May 23 00:37:03 2013, 美东) 提到:
在承认素数的这个等价定义 (即 a是素数 <=> a是大于1的自然数, 且a不被任何小于a
的素数整除) 的前提下, 居然有人会认为这个证明是错的, 或者是不完备的.
我实在不能理解.
求问一下大家, 是不是有的人的脑子天生有缺陷, 根本怎么教都不会明白... 阅读全帖 |
|
n*****n
发帖数: 567 | 44 不觉得奇怪
计算机科学里面的计算和计算数学中的计算意义并不一样，我觉得。
CS里面的计算是基于图灵机的，指算法（有效的过程），分析
可计算性（分析一个问题的是不是可以被一个图灵机判定等），
复杂性（算法＝图灵机 的时间空间复杂性）
而计算数学里面的计算具体的指在计算机上实现方程等数学问题
求解的方法，重点分析收敛性。
计算数学里面的数学指连续性的数学分析等。
CS则重点在离散数学。
叫
是
没
数 |
|
l******t
发帖数: 55733 | 45 你这个就是一种表达式。图灵就是从表达式入手搞图灵机的。只能理论根本不能真正实
现。因为你无法实际给所有表达式编号。也不能揭示表达式之间的任何关系。图灵机就
像归纳法。虽然正确但感觉就是隔着丝袜摸大腿嘛。
lambda明显更深刻只要3个规则就够。万般皆可从lambda来。可以直接从lambda运算中
抽象category或者应用category。对比图灵机lambda那就是直入小穴了，爽翻天啊。
至于oo，啥数学支撑没有，左的没边了。鼓吹OO的都应该枪毙15分钟。 |
|
l******t
发帖数: 55733 | 46 你这个就是一种表达式。图灵就是从表达式入手搞图灵机的。只能理论根本不能真正实
现。因为你无法实际给所有表达式编号。也不能揭示表达式之间的任何关系。图灵机就
像归纳法。虽然正确但感觉就是隔着丝袜摸大腿嘛。
lambda明显更深刻只要3个规则就够。万般皆可从lambda来。可以直接从lambda运算中
抽象category或者应用category。对比图灵机lambda那就是直入小穴了，爽翻天啊。
至于oo，啥数学支撑没有，左的没边了。鼓吹OO的都应该枪毙15分钟。 |
|
d***a
发帖数: 13752 | 47
。）
给学生改过文章的人一般都知道，写的太垃圾的东西，其实是非常不容易纠正的。
关于Enigma，懂的人都知道那不过是图灵的副业。有人爱乱捧图灵，那又不是图灵的错
。真正的砖家，看了后也就一笑了之罢了，哪会象王垠这么唠叨个没完。
后来居然还有一大段他对图灵心理活动的揣测...这活生生是一个编程过多，头脑僵化
，心理不太正常的程序员形象。
图灵对计算机界最大的贡献，是图灵机模型和相关理论与论断。图灵机一种用于分析可
计算性和计算复杂度的工具，并不是直接拿来编程的，这是常识。王垠说的是: “图灵
机的设计是丑陋，复杂，缺乏原则的。它的读写头，纸带，状态，操作，把本来很简单
的语义搞得异常复杂。“ 可是，图灵机是研究计算机理论的工具，难要做的和Java一
样？王垠这是脑子不清楚。
王垠这家伙就象一个B+的学生，以为自己很了不起，象个老太婆一样整天唠叨。他说的
那些东西，对拿C的学生来说，听起来可能新鲜，对砖家来说，读起来如同嚼蜡，没什
么内容。 |
|
w***g
发帖数: 5958 | 48 用存储在介质上的程序来控制机器这个概念自古就有。音乐盒拆播放什么音乐就是由
金属片上不同位置的突起点控制的。巴贝奇造差分机是也是这么做的，Ada Lovelace
写得程序先在还能够看到。这个才是现代计算机真正的祖宗。巴贝奇的机器最终没有
造出来是因为当时蒸汽－机械科技枝的局限。电子器件出现后，即使没有Church没有
Turing，计算机一样会被造出来的，而且存储程序计算机在当时的历史条件下是唯一
的可能。从古至今，lambda calculus只存在于纸上，或者软硬件图灵机的模拟中。
沿着lambda calculus走，走到头无非就是数学。沿着图灵机走才能走出来计算机科学
和现在的IT业。图灵的贡献在于把程序控制机器这种做法理论化了，建立了一个严格
的用来研究算法及其复杂度的框架，并且证明了这种看似粗糙的做法在理论上的
自洽性。这个基本上就是后来整个CS发展的大前提。Lambda calculus里既没有时间
概念又没有空间概念(先在当然都可以倒推回去)，基本上就是然并卵。放100年前
看不到图灵机在实践上的优越性，可以说是没有远见。先在还看不到或者不愿意看到，
也怪不得他PhD... 阅读全帖 |
|
x****u
发帖数: 44466 | 49 你看一下确定性图灵机的定义，要求每一步都确定的。
如果做不到就不是确定图灵机了，这个在数理逻辑里面很重要啊。30年前已经知道AI通
过确定图灵机实现难度不弱于NPC问题，所以当时的AI才迅速进入寒冬期，除了日本政
府不学无术的官员上当，别人都不正经投钱了。 |
|
g****t
发帖数: 31659 | 50 假设所有确定性图灵机的结果的集合是A。
那么有限输入的随机图灵机的结果属于A。
因为随机数是有限输入的，所以可列举成多个确定性图灵机。
所以其结果已经包含在A内。尽管它是多个结果。
So it is clear that Random machine can not output an un-computable number.
Even the probability version is a NO.
"Supposing that we give a Turing machine random input, is it possible for
the machine's output to be complete and consistent with nonzero probability?
The answer is no." By a theorem due to de Leeuw, Moore, Shannon, and Shapiro
(1956)
http://mathoverflow.net/questions/224143/can-a-stochastic-tur... 阅读全帖 |
|
