n********g
发帖数: 6504 | 1 数学证明作为一种运算有两种：存在性证明及构造性证明。寻找配偶、结婚以及跑家庭
，作为运算，也同样跑不出可计算性及计算复杂性。
所谓可计算性问题就是，无论一个社会的结构价值体系如何，总有角色是找不到配偶的
。当然人是活的，希望她们能够意识到这一点，早日转换角色走出社会的阴影。
假设可计算性不是问题，存在配偶的可能。但是证明存在配偶的计算复杂性对于各社会
角色是不同的。有些角色很简单就能证明（如只需要多项式时间），有些角色很复杂（
如需要指数时间）。
相比之下，存在性较好证明，而构造性（找到符合条件的一个实例）较难。虽然我证明
了（多数情况下）存在就一定能找到。但找到的复杂性还是可能远远超过证明存在的复
杂性。因此，不奇怪的是，人如果不改变自己的期望，短暂的一辈子里找不到配偶一点
都不奇怪。
再进一步，找到了配偶，结了婚，也还有计算复杂度问题。在变动的环境中维持婚姻的
稳定，同样需要做功。不同的婚姻有不同的计算复杂度（维护成本）。一段婚姻超过了
计算能力，算不下去而停机reject，也是可以预期的。
和传统的感性认识不同，可计算性和计算复杂性分析有着严格的数学基础，可以量化婚
姻的成本，合... 阅读全帖 |
|
发帖数: 1 | 2 【和传统的感性认识不同，可计算性和计算复杂性分析有着严格的数学基础，可以量化
婚姻的成本，合理安排自己的生命及端正自己的预期。各位年轻人应该关注一下。】
现代哲学，难道你搞懂了。。。。？？？中国人能把empericism是什么搞清楚，不在那
里天天叨逼什么行而上学。。我看就是进入文明时代的开始了。。。。 |
|
d***a
发帖数: 13752 | 3 如果说的是可计算性理论，确实是这样，在实际中直接能用到的不多。没有谁会写程序
去解一个不可解的问题。:)
但可计算性理论和图灵机，是算法设计和算法复杂度分析的理论基础之一，而算法设计
对编程来说是非常重要的。所以一个好的程序猿，多多少少应该知道一点可计算性理论。
王垠做的应该是编程语言设计。辩论Java牛还是python牛，他大概是一把好手，但那些
和计算机理论，特别是可计算性理论这样基础性的理论，差得很远。王垠这家伙就是吃
饭了发发牢骚，不用当真。 |
|
s*******w
发帖数: 2257 | 4 华夏文摘】老钱：硅谷传奇：计算机发展简史- -（附录）
发表于 2016 年 04 月 22 日 由 老钱
人类的进步主要由两个部分组成：一是人类的组织原则和组织结构的进步，另一个是科
学技术的进步。近代以来，人类在组织原则和组织结构方面的进步相对比较缓慢。但是
，科学与技术则有了翻天覆地的变化。用理工科的说法就是，以往的世代里，科技进步
是线性的，近代以来则是以指数形式在发展。近代的科技发展，赋予了人类无以伦比的
力量。这么说吧，要是把人类和地球上其他物种进行比较的话，今天人类的能力堪比上
帝。
十八世纪的第一次工业革命给我们带来了蒸汽机，人类在力量、速度、和距离上开始主
宰世界，这是力学与热学综合应用的产物。十九世纪和二十世纪初的第二次工业革命，
给我们带来了新能源，电力、石油、化工等等新兴产业主宰了我们的日常生活，尽管这
次工业革命也带来了一场世界性的农业革命，但从此人们对土地的依赖越来越弱了。这
是热力学、电磁学、化学综合应用的产物。到了二十世纪末，一场彻底改变人类传统生
活方式的工业革命发端了。这是以技算机、互联网、无线通讯兴起的产业革命。这是以
量子力学为代表的近代物理的综... 阅读全帖 |
|
发帖数: 1 | 5 歪了那么久的楼。说说计算机如何进行推理。
康托尔：定义了数；罗素：一切东西都可以用一个（整）数表示；图灵：定义了通用机
器算这些数
你可以把一个（图灵机的）排列组合用一个整数表示出来。图灵机每算一步，数变了，
就等价于一步推理。整个推理过程就是迭代的过程。图灵的老师邱奇用函数计算表达这
一（推理）过程。北大版讨论可计算性时也是用函数的方式。是我读到的唯一用函数方
式讨论此问题的。怕是哪作者死了就所有人都用图灵机了。
这个数，也就是code。构造这个数的过程就是coding。构造一个机器对应的数的过程是
一种特殊的coding，用人话说就是编程。大多数CS在干的就是在不同的层次编程。有了
code，就可以在通用机器上跑模拟特定的机器得出计算结果。
1+1是计算，计算不限于1+1。不要把一帮学应用数学出身搞出来的东西代表CS。这些人
怕是计算是什么都不知道。“计算”可以解释薛定谔猫。压根就不需要引入什么智慧生
物。物理上的“观察”就是一种计算。照相机、底片就是程序。人的观察就是计算。如
果不计算，你不知道计算结果（图灵的不可计算性，没有办法不经过实际的计算得知计
算结果）。
你说计算机不能... 阅读全帖 |
|
发帖数: 1 | 6 歪了那么久的楼。说说计算机如何进行推理。
康托尔：定义了数；罗素：一切东西都可以用一个（整）数表示；图灵：定义了通用机
器算这些数
你可以把一个（图灵机的）排列组合用一个整数表示出来。图灵机每算一步，数变了，
就等价于一步推理。整个推理过程就是迭代的过程。图灵的老师邱奇用函数计算表达这
一（推理）过程。北大版讨论可计算性时也是用函数的方式。是我读到的唯一用函数方
式讨论此问题的。怕是哪作者死了就所有人都用图灵机了。
这个数，也就是code。构造这个数的过程就是coding。构造一个机器对应的数的过程是
一种特殊的coding，用人话说就是编程。大多数CS在干的就是在不同的层次编程。有了
code，就可以在通用机器上跑模拟特定的机器得出计算结果。
1+1是计算，计算不限于1+1。不要把一帮学应用数学出身搞出来的东西代表CS。这些人
怕是计算是什么都不知道。“计算”可以解释薛定谔猫。压根就不需要引入什么智慧生
物。物理上的“观察”就是一种计算。照相机、底片就是程序。人的观察就是计算。如
果不计算，你不知道计算结果（图灵的不可计算性，没有办法不经过实际的计算得知计
算结果）。
你说计算机不能... 阅读全帖 |
|
h*h
发帖数: 27852 | 7 http://www.yinwang.org/blog-cn/2015/10/18/turing
图灵的光环
仿佛全世界的人都知道，图灵（Alan Turing）是个天才，是他创造了计算机科学，是
他破解了德国纳粹的Enigma密码。由于他的杰出贡献，计算机科学的最高荣誉，被叫做
“图灵奖”。然而根据自己一直以来对图灵机等计算模型的看法，加上一些历史资料，
我发现图灵本人的实际成就，相对于他所受到的崇拜，其实相差甚远。
由于二战以来各国政府对于当时谍报工作的保密措施造成的事实混淆，再加上图灵的不
幸生世所引来的同情，图灵这个名字似乎拥有了一种扑朔迷离的光环。人们把很多本来
不是图灵作出的贡献归结在他身上，把本来很平常的贡献过分地夸大。图灵的光环，掩
盖了许多对这些领域做出过更加重要贡献的人。
图灵传
2012年，在图灵诞辰一百周年的时候，人们风风火火的召开各种大会，纪念这位“计算
机之父”，很多媒体也添油加醋地宣传他的丰功伟绩。还有个叫Andrew Hodges的人，
抓住这个时机推销自己写的一本传记，叫做《Alan Turing: The Enigma》。这本书红
极一时，后来还被改... 阅读全帖 |
|
z**********e
发帖数: 22064 | 8 http://hx.cnd.org/?p=123650
老钱
人类的进步主要由两个部分组成：一是人类的组织原则和组织结构的进步，另一个是科
学技术的进步。近代以来，人类在组织原则和组织结构方面的进步相对比较缓慢。但是
，科学与技术则有了翻天覆地的变化。用理工科的说法就是，以往的世代里，科技进步
是线性的，近代以来则是以指数形式在发展。近代的科技发展，赋予了人类无以伦比的
力量。这么说吧，要是把人类和地球上其他物种进行比较的话，今天人类的能力堪比上
帝。
十八世纪的第一次工业革命给我们带来了蒸汽机，人类在力量、速度、和距离上开始主
宰世界，这是力学与热学综合应用的产物。十九世纪和二十世纪初的第二次工业革命，
给我们带来了新能源，电力、石油、化工等等新兴产业主宰了我们的日常生活，尽管这
次工业革命也带来了一场世界性的农业革命，但从此人们对土地的依赖越来越弱了。这
是热力学、电磁学、化学综合应用的产物。到了二十世纪末，一场彻底改变人类传统生
活方式的工业革命发端了。这是以技算机、互联网、无线通讯兴起的产业革命。这是以
量子力学为代表的近代物理的综合应用的产物。
在今天的世界里，对人们日常生活... 阅读全帖 |
|
H********g
发帖数: 43926 | 9 【 以下文字转载自 Military 讨论区 】
发信人: hsh (nidaye), 信区: Military
标 题: 王垠： 图灵的光环
发信站: BBS 未名空间站 (Mon May 9 12:34:11 2016, 美东)
http://www.yinwang.org/blog-cn/2015/10/18/turing
图灵的光环
仿佛全世界的人都知道，图灵（Alan Turing）是个天才，是他创造了计算机科学，是
他破解了德国纳粹的Enigma密码。由于他的杰出贡献，计算机科学的最高荣誉，被叫做
“图灵奖”。然而根据自己一直以来对图灵机等计算模型的看法，加上一些历史资料，
我发现图灵本人的实际成就，相对于他所受到的崇拜，其实相差甚远。
由于二战以来各国政府对于当时谍报工作的保密措施造成的事实混淆，再加上图灵的不
幸生世所引来的同情，图灵这个名字似乎拥有了一种扑朔迷离的光环。人们把很多本来
不是图灵作出的贡献归结在他身上，把本来很平常的贡献过分地夸大。图灵的光环，掩
盖了许多对这些领域做出过更加重要贡献的人。
图灵传
2012年，在图灵诞辰一百周年的时候，人们风风火火的... 阅读全帖 |
|
wy
发帖数: 14511 | 10 先来一点补充：
Church's Thesis: 所有通用计算机可以解决的问题，图灵机都
可以解决，换句话说就是图灵机的计算能力和通用计算机完全一样，
不多也不少。所以我们才可以使用图灵机解决以下问题：可计算性与
计算复杂性。
可计算性就是说，什么问题是计算机可以解决的，而什么问题是不可以的。
计算复杂性就是说，对于可以解决的问题，我们可以以什么样的成本去解决。
计算复杂性的问题，首先说一下为什么计算机科学家认为NP问题
对于决定性机器而言其产生的障碍是本质的。
举个例子，如果我们假定n=1时为了解决问题，计算机需要执行1条指令，
在假设每条指令执行时间等长，那么n=2时，对于一个NP问题，计算机需要
执行2条指令...那么n=n1时，计算机就需要执行2^(n-1)条指令，现在
我们就算有一台无比强大的机器，他的速度达到2^10000指令/秒，可是，
如果这时候n=100000,他的执行时间仍然达到2^90000秒！大家可以试试，
如果一个多项式时间的算法，情况如何。
计算复杂性问题可以通过量子计算机（非决定性图灵机）得到缓解，但是
不是解决！因为除了NP class,还存在有成本更高 |
|
s*****l
发帖数: 15 | 11 有一门专业课，是限选 -- 在给定的两三门里选一门。计算机系
有一门这样的课，限选范围是：可计算性，运筹学。吾先去听了
两次可计算性，发现在先生面前吾的智商是零，于是决定选运筹
学 -- 以为自己数学功底好，能对付。
这门课是数学系的姚恩瑜老师开给她的唯一的弟子的，去了几个
我们凑热闹的，一共才6个人。于是地点就选在欧阳纯美楼一楼的
教室里。教室很小，六张课桌分两排放。这也是吾仅有的去欧阳
纯美楼的正当理由和原因 -- 好象不是每个浙大学子都有机会进
欧阳纯美楼的。欧阳纯美楼的最给吾留下印象的是卫生间，除了
邵科馆，那的卫生间是全浙大最干净的。
姚老师原先是研究生院副院长 -- 妇女政策的结果。她上课可谓
驾轻就熟，讲得飞快。开始吾还跟着思考，还知道下一个公式是
如何由前面几个推出来的。半学期后，只有狂记笔记的份了。
考虑到只有几个学生，而且要记的定理、公式较多，姚老师决定
让我们开卷考。
考试原定八点半到十一点，时间到了，我们都没做完，包括她的
嫡系弟子。于是延长到十二点，问我们可不可以交卷了。我们说
不行。只有她的弟子犹豫了半天，交了。姚老师又给我们延到下
午一点。要不是一方面实在 |
|
h*h
发帖数: 27852 | 12 【 以下文字转载自 Military 讨论区 】
发信人: hsh (nidaye), 信区: Military
标 题: 王垠： 图灵的光环
发信站: BBS 未名空间站 (Mon May 9 12:34:11 2016, 美东)
http://www.yinwang.org/blog-cn/2015/10/18/turing
图灵的光环
仿佛全世界的人都知道，图灵（Alan Turing）是个天才，是他创造了计算机科学，是
他破解了德国纳粹的Enigma密码。由于他的杰出贡献，计算机科学的最高荣誉，被叫做
“图灵奖”。然而根据自己一直以来对图灵机等计算模型的看法，加上一些历史资料，
我发现图灵本人的实际成就，相对于他所受到的崇拜，其实相差甚远。
由于二战以来各国政府对于当时谍报工作的保密措施造成的事实混淆，再加上图灵的不
幸生世所引来的同情，图灵这个名字似乎拥有了一种扑朔迷离的光环。人们把很多本来
不是图灵作出的贡献归结在他身上，把本来很平常的贡献过分地夸大。图灵的光环，掩
盖了许多对这些领域做出过更加重要贡献的人。
图灵传
2012年，在图灵诞辰一百周年的时候，人们风风火火的... 阅读全帖 |
|
p********r
发帖数: 593 | 13 方滨兴：我在家也翻墙 武大演讲被扔鞋
时间:2011-05-20 11:43来源:思想潮 作者:思想潮综合 点击:579次
5月19日上午，方滨兴将前往武汉大学参加一项学术活动的消息在微博迅速传开。有网
民发帖称下午方滨兴将出现在武汉大学计算机学院B座4楼，很快一项随手扔方校长解救
中国互联网的悬赏活动展开，扔中方滨兴的悬赏起初是10个VPN账号，随后又有淘宝网
2000元订单、
5月19日上午，方滨兴将前往武汉大学参加一项学术活动的消息在微博迅速传开。
有网民发帖称“下午方滨兴将出现在武汉大学计算机学院B座4楼”，很快一项“随手扔
方校长解救中国互联网”的悬赏活动展开，扔中方滨兴的悬赏起初是10个VPN账号，随
后又有淘宝网2000元订单、香港大餐、苏州园林套票，甚至美女香吻拥抱。不过，武汉
大学官网却没有任何关于此事的消息。
下午，来自微博尚未证实的消息称，现场有人向方滨兴投掷鸡蛋未中，继而脱下鞋
子，“第一支鞋打中了，第二只鞋被一男一女护住了”。微博称现场发生冲突，有十余
人追出，准备抓住扔鞋的抗议者，但在学生的阻拦中，抗议者离开了现场。
随后有学生在微博称自己赶到计算机学院4楼... 阅读全帖 |
|
i***s
发帖数: 39120 | 14 北方邮电大学校长方滨兴昨日前往武汉大学参加一项学术活动的消息在微博迅速传开。有网民发帖称“下午方滨兴将出现在武汉大学计算机学院B座4楼”，很快一项“随手扔方校长解救中国互联网”的悬赏活动展开，扔中方滨兴的悬赏起初是10个VPN账号，随后又有淘宝网2000元订单、香港大餐、苏州园林套票，甚至美女香吻拥抱。不过，武汉大学官网却没有任何关于此事的消息。
《云南信息报》报道，下午，来自微博尚未证实的消息称，现场有人向方滨兴投掷鸡蛋未中，继而脱下鞋子，“第一支鞋打中了，第二只鞋被一男一女护住了”。微博称现场发生冲突，有十余人追出，准备抓住扔鞋的抗议者，但在学生的阻拦中，抗议者离开了现场。
随后有学生在微博称自己赶到计算机学院4楼时，发现有数名保安和师生“把守”。其透露16时30分，两名警察上楼，一群人围着方滨兴离去，戒备随之解除。
一名年轻男子在人人网介绍，当日计算机学院内部贴出的“863代表团考察”通知中丝毫没有提及方滨兴。这名青年称现场警戒森严无法进入会场，随后其在楼内手举“404 NOT FOUND”字样纸条留影。而据网络传言，方滨兴昨日下午的学术活动正在计算机大楼B404。
武汉大学计算... 阅读全帖 |
|
i***s
发帖数: 39120 | 15 广西师范大学出版社今年2月出版的《一个独立教师的语文之旅》是“独立语文教师”郭初阳近年来对语文教育的评论合集，包括学科建设、教材批评和对教师身份的思考。曾经多次获得全国课堂教学大赛第一名的他，如今已离开学校。但对于学校语文教育，他有着源于课堂而超越课堂的见解。
“教育的麦当劳化”
在《一个独立教师的语文之旅》这本书中，郭初阳对当下的语文教育多有批判。如，让少年硬读、硬背古书，写作不重视虚构能力和想象力的培养，缺乏性教育和死亡教育等。
他把当下的学校教育用“教育的麦当劳化”来概括。它包含4个特征：一是追求效率，越快越好。麦当劳食品生产讲求高效率。学校教育则把知识快速灌输到孩子脑中，对时间的控制同样非常精准；二是可计算性，凡事都能量化。麦当劳食品讲求规范化。在学校，各门学科也都变成一个分数。甚至生活也能量化，如，寝室整洁程度、着装，都可以打分；三是可预测性。麦当劳无论在北京、上海还是杭州其食物讲求一统化。全国的学校也整齐化一、缺乏特色。四是缺乏人性化。麦当劳在服务规范使员工的着装和对话经过训练，但在学校有着诸多刚性规定。学生按点上课、做眼保健操、发言要举手，老师则用统一方式教授指定内容。
... 阅读全帖 |
|
f****u
发帖数: 63 | 16 你到底了不了解计算机啊？
美国从一开始就甩开了全世界，怎么是同一起跑线呢？
从Tuning的可计算性研究, 到von neumann的计算机体系，
到第一台电子计算机，都是在美国雄厚的科研和工业基础上产生的。
到现在，美国整个计算机科研和工业还是拥有比其他国家更加雄厚的实力。
中国一直在追赶，现在计算机科研和工业开始有很多亮点了。
中国计算机现在还超越不了美国，但比倭国还是强不少的。
我奉劝你，哗众取宠之前，先做点功课，了解一下再说。 |
|
b***m
发帖数: 891 | 17 离职报告
尊敬的领导：
你们好！
2006年8月，我一手拎着席子，一手抱着被子到学校来报到，工作。在办公室地板上睡
了3个晚上后，在XXX街XX坊和别人合租了一间房子，每月800元。自己感觉还好。但是
，当我的妻子到上海来看我的时候，却大哭了一场。她没有料到这个能写优美散文，中
英文俱佳，十年前的月薪就有3千元的男人却如此落魄：房间里没有像样的可以工作的
桌子，没有坐的地方，只能坐在床上；办公室也没有她可以坐的地方。是的，到现在，
我的办公室也只有一把椅子，一台普通的惠普激光打印机还是妻子送给我的生日礼物。
在妻子的坚持下，2007年3月，和别人合租大半年后，我搬到了XX新村X舍X号X室（证明
人：上XXXX学院XXX），月租金1600元。
我到学校来的唯一任务是做科研。不上课，也不带学生。我做的专业是理论物理。在我
看来，当前理论物理的基本问题可以分为三个方面，也是三个层次：最前面的，也是最
浅层的，是粒子物理里面的质量问题，中微子问题，粒子态混合问题；其次的，更难一
些的，是自洽地统一描述引力场和量子场；最后的，最难的，是真正的宇宙学，宇宙的
概念是万物都包含在内的，真正的宇宙学应... 阅读全帖 |
|
o**o
发帖数: 175 | 18 井底之蛙，知道可计算性，NP问题吗？知道AI吗？
知道scalable分布式计算需要解决的问题吗？ |
|
b*******8
发帖数: 37364 | 19 弃医也不见得有道理
生物体内部极其复杂决定因素太多，搞出五行这样一个模型，可以认为是参数归并简约
出来的一个近似模型，具有比较好的近似度和可计算性。至于模型里的每个参数，不一
定要有实体对应。统计和数据挖掘里面就有大量这样的例子
验药，也要验医 |
|
n**********5
发帖数: 1707 | 20 你把危机百科里的图灵机，可计算性，计算复杂性等东西看懂，看不懂背下来。特别是
NP是啥千万别搞错。最好用高级语言写一个图灵机。麻婆interview的时候就跑不掉了
。被问到不懂或百科里没提过的部份千万别脸红，就说这个问题你还在想。99%的码公
不懂图灵机。如果你能把对角线法弄懂，已经秒杀99.9%的码公了，名笑博士都大半被
你斩于马下。如果你还能说出康托尔、哥德尔的大名，深情回忆康托尔如何撩开上帝的
面纱最终死在精神病院，这辈子你软饭就有着落了。大叔我上知天文下懂地理，古今中
外，全没用上。就凭图灵机就够用了。 |
|
P***y
发帖数: 2885 | 21 这个要顶。当年俺就是提了一下哥德尔和图灵机。
：你把危机百科里的图灵机，可计算性，计算复杂性等东西看懂，看不懂背下来。特别
是NP是啥千万别搞错。最好用高级语言写一个图灵机。麻婆interview的时候就跑不掉了
：。被问到不懂或百科里没提过的部份千万别脸红，就说这个问题你还在想。99%的码公 |
|
n**********5
发帖数: 1707 | 22 北大的教材是很牛。有机会我上一张书架照。一本北大的可计算性小册子愣是用非图灵
机方式写出来。
听说过一东欧的牛人证明了CS里的伟大定理。我就知道自己没法混天牛。人家1个星期
做出来的东西我3个月到1年都不一定能做出来。
那一套从集合论为基础的数学书是任何想投身严肃数学研究的必读。举例说数学归纳法
为何有效。什么时候无效。看集合论。
我没有听过这个人究竟做了什么划时代的贡献。我记得一个数学教授说过，你发paper
之前先想一想：全世界那么多人，why you能正确地证明了这个定理。不过读了这位大
神的事迹，大概能够感觉到why not me。呵呵。
神。 |
|
i******0
发帖数: 609 | 23 即使抛开对＂智能＂哲学层面上的思辩，可计算性理论，哥德尔不完备性定理等等已经
在数学层面对现有的计算模型和数理逻辑方面给出了清晰的能力上界。
从这个意义来说，担心创造出超越人的智能的机器或系统基本等同于杞人忧天；反过来
说，这样的企图基本等同于永动机的实验。
：没错，就是这个总的purpose，不可能自己产生，必须由creator赋予。类似阿西莫夫
的机器人三定律，就是这种东西。理论上讲，现在的人工智能技术继续进步，就能到达
阿西莫夫的机器人这个水平。
：如果把人也看作一个很复杂的机器，引申出来很有意思的问题就是人的purpose是谁赋 |
|
i******0
发帖数: 609 | 24 建议你学习一下可计算性(Computability)理论，可以从＂停机问题＂(Halting
Problem) 开始。
这是个理论上界，人类的努力在它面前没有什么意义。就好比如果有人声称造出了永动
机，你并不需要对其进行检验就可以知道那是不可能的。
：坦白说不懂你的逻辑，现有的计算模型和数理逻辑的上界和机器不能超越人有什么相
关性？除非你证明人类已经到达这个上界。
：【 在 idong360 (bull) 的大作中提到: 】 |
|
发帖数: 1 | 25 99%的博士不懂图灵机。在我看来，P vs NP也许不难。但如果你不懂图灵机，你怎么看
的懂这个问题。
世界上没有无缘无故的爱恨。北京大学是我读过唯一使用lamda函数描述可计算性问题
。（换一个角度讲是不是中国就没人明白图灵机是什么。）但是问题是你的数是怎么定
义的。连数都没有定义，你搞什么函数转换/计算。
图灵机恰恰定义了数。我相信，这正是康托尔和罗素思想的传承。康托尔没兴趣搞图灵
机。是因为图灵机只是康托尔体系里最差的子集。而图灵机之上还有无数的层级。
文科生眼里不可思议的智能机器，连图灵机的能力的零头都没达到。康托尔宣称他掀开
了上帝的面纱（然后死在精神病院）。我觉得一点都不夸张。
科学是老老实实的学问。知之为知之，不知为不知。对自己不懂的东西表态要慎重。写
了几天代码的码工连码工这个词是图灵机定义的都不知道。就要闹出天大的笑话。 |
|
发帖数: 1 | 26 但是也有好处---大大地提升了他的历史地位，
因为正好符合了当时的性解放的政治需要。
其实可计算性完全是哥德尔搞定的，
不知道有Church/Turing什么事。 |
|
d*****u
发帖数: 17243 | 27 算法课不同学校讲的差异其实挺大的
有的侧重复杂度分析，有的侧重可计算性
有的讲很多图算法，有的压根不讲
有的动态规划讲半个学期，有的一节课 |
|
t**8
发帖数: 4527 | 28 离散数学是计算机本科要学习的计算机基础理论
传统上， 计算机软件三大块
操作系统， 语言编译 和 数据库
这三大块无一例外的用C／C++ 编写， 只是有机会做这些基础的工作的人很少很少
比如 数据库， 是指设计数据库系统， 而不是 用SQL 编程
Internet 火了以后， 网络应用编程多了起來， 这部分其实不属于计算机软件
概率统计 数值优化 数值计算 与计算机科学没有任何关系， 计算机科学硕士以上学位
要求是 Computability theory
中文翻译是可计算性理论
你可以说计算机科学在实际编程中没用， 其实我们学的科学文化知识 99% 都是没用
的， 不论你做什么工作 |
|
t******l
发帖数: 10908 | 29 实际上这个无限深度二叉树，或者说，infinite permutation with repetition tree
，也不是简单的在 希尔伯特旅馆 和 cantor diagonal argument 之间。
实际上从某个角度看，这个比 cantor diagonal argument 还要大，因为 leaf node
的集合，跟 cantor diagonal argument 的实数行可以一一对应，因为都是
permutation with repetition。。。但 cantor diagonal argument 这下是孙悟空逃
不出如来佛的手掌心。
但另一方面看，如果我做 breadth first traversal，这玩意儿就好像跟希尔伯特旅馆
一样大不是？
其实这个悖论是设计的，在 cantor diagonal argument 时，flip 二叉树的某个节点
，实际上是从树叶那边看过来的，于是每个节点很大很大。。。这使得 cantor
diagonal flip bit 造成个很大很大的跳跃，使得 cantor diagonal argument 跳不出
如来佛... 阅读全帖 |
|
t******l
发帖数: 10908 | 30 但 cantor 的第一个问题，是没有刷过 leetcode，没有注意到可计算性以及香浓有限
信息量的情况。。。（当然，cantor 也可能早就知道，但是作为高维生物玩弄一下低
维生物，所以 cantor 故意不说）。
这样这个 permutation (with repetition) on infinite length sequence，直接生生
造出了许许多多以前从来没看到过的“不可计算数”，原因是那种数的香浓信息量无穷
大。。。（顺便说一句，sqrt(2) 是可计算数，虽然是无限不循环小数，因为其携带的
信息量不是无穷大，或者说有有限长度的生成规则产生，即使序列长度是无穷长且没有
肉眼直接看得见循环 pattern，这不等于没有理论上的 pattern。。。当然这又要回到
哥德巴赫猜想，是不是所有的 pattern 都基于同余循环的问题）。
这种不可计算数多如牛毛的程度，到不管是 dedekind cut 随便来一刀，还是 cauchy
sequence 随处震三下，其结果是数学上严格精确的 100% 的概率出现的是不可计算数
，数学上严格精确的 0% 的概率出现的是可计算数... 阅读全帖 |
|
t******l
发帖数: 10908 | 31 我作为民科忘了概念的角度讨论，我觉得如果把时空建模成康托的实数集，那么确实没
有可实现的实数集合上的对于任何输入都可以的理想高频截断滤波器。。。因为可实现
的滤波器有限时域窗口长度的限制，会导致违反因果律，或者可计算性。。。或者另一
个角度，把滤波器有限时域矩形窗口本身做 Continuous Fourier Transform，应该得
出一个坑爹无限区间的函数不是？
当然提一下图像处理跟实时信号处理还有细微差别，实时信号处理的时域窗口长度还受
制于最大允许延迟的要求。图像处理是整张图读进来处理，在空域操作，没有最大允许
延迟一说。
而马工实践上都是有限离散，所以实践上只要处理器够强大，理想数字高频截断，或者
理想数字带阻截断随便啥都可以（当然数字带阻的实时系统的话，最高通过频率受制于
延迟，但图像处理不是实时信号处理，没有延迟的问题）。
大不了对整个图像 DCT 一次（有限离散不是？)，高频中频截断反向 DCT 一次，用个
nVdia 图像卡指令集齐活收工。
但这本质上是基于自然数集的有限离散 Fourier Series 而不是实数集上的 Fourier
Transform ，避... 阅读全帖 |
|
G****r
发帖数: 5579 | 32 Computer Science: 数学的一个分支， 主要研究可计算性和计算复杂性。
Computer Engineering， Electrical Engineering 都算工程。 EE 里有些专业或研究
方向可以算是应用物理。 |
|
发帖数: 1 | 33 这个主题很好。
婚姻家庭是NP问题，没有铁律。 |
|
发帖数: 1 | 34 我真的受不了你了。。。
is that necessary?
So, you don't want to see me.Right? |
|
发帖数: 1 | 35 就两种算法
有钱就买一个，没钱就抢一个。
中间值全部取false |
|
发帖数: 1 | 36 德里达的解构就是扯几把蛋！！！！deconstruction....
存在性=定性
你对着一堆文盲卖弄这些个哲学名词，是想给我个人刷存在感吧。。。
我心里只有一个GS..你别刷了。。买买提虽然很low比不需要你交版面费。。你要是
跟我一样刷屏，版主照样封你。。。。 |
|
|
n********g
发帖数: 6504 | 38 不要啥觉得复杂的东西都往NP里塞。
不确定图灵机对应的是存在性问题。确定图灵机对应的是构造性问题。
所谓说不zuo不die。如女人说no男人该如何理解就是NP问题。存在一个（她认为）简单
的解；但要构造出一个能解出来的男人可能性则随着no的东西多了指数递减。 |
|
|
发帖数: 1 | 40 关死我了！
有没有学过＂Theory of Computation”? |
|
|
发帖数: 1 | 42 我只是想由浅入深的来将这个道理。。。。。。
我是一个科学家。。
出来卖，都一样。。。 |
|
发帖数: 1 | 43 研究在人，得奖在天。弄个炸药级研究还是有可能的。
按照可计算性理论，不老和不死是不可能的（理论不能解释的），因为不老和不死是算
不出来的（永不停机）。
不过平衡让俺秒杀所谓20多岁的鲜肉，不化妆，也很美丽冻人，则没有任何问题。
女人最怕自己变老。跟着俺就不用焦虑不用PS了。广告贴啊广告贴啊。 |
|
m**********e
发帖数: 12525 | 44 牛个鸡巴，可计算性是人church发明的，连理论都叫church-turing theory
因为丫是英国人，英国现在完蛋了，找不到人吹，于是死捧turing
这跟捧霍金是一个套路 |
|
发帖数: 1 | 45 church 和Turing 分别建立了两个不同的计算模型
合作一篇文章证明两者等价
: 牛个鸡巴，可计算性是人church发明的，连理论都叫church-turing
theory
: 因为丫是英国人，英国现在完蛋了，找不到人吹，于是死捧turing
: 这跟捧霍金是一个套路
|
|
i******0
发帖数: 609 | 46 这个不是他让不让的问题。冯诺伊曼在计算机领域的地位本来就没你以为的那么高。不
知道什么原因，二十多年前的国内计算机教材把他捧得很高，对真正的奠基人图灵却一
笔带过，只说图灵奖是计算机界的顶级荣誉。
图灵之所以有那么高的地位是因为他的模型令人信服地解决了什么是effectively
computable的定义的问题。尽管大家目前还是用Church-Turing Thesis来定义它，但是
在众多包括Church的lambda calculus, Godel-Herbrand General Recursion等等与之
等价的计算模型中，Turing Machine更准确地定义了可计算性的上界。歌德尔在1936年
看到图灵的论文后对其模型很推崇。
奉劝楼主一句，自己不懂的领域别光靠看点演义性质的资料就出来得瑟。
：不要脸的牛人多了去了，特别是当代。所以他能够不占别人便宜，主动让credits,就
是值得称道。
： |
|
发帖数: 1 | 47 这等价于图灵机的可计算性。
也许存在比图灵机更强大的存在，但这一计算模型不能被物理过程所模拟。
这算是图灵教的一条公理假设。 |
|
发帖数: 1 | 48 1. 你先给个“countable数”的定义先。希尔伯特旅馆是讨论无穷数集的概念，和可数
不可数无关。只要是无穷集合都可以有希尔伯特旅馆悖论，无论可数还是不可数。
2. 不管你那个荒唐的countable超越数是怎么定义的，一个数要么是countable,要么不
是countable,什么叫数出来的超越数会不一样?
3. 这个超越数集不可数是对的，但超越数的定义和可数不可数屁关系都没有。
总之你就是典型的在课上或者科普读物里学了几个名词，但对这些概念根本一窍不通，
还老爱拿这些名词出来唬人的民科。
关于2再教你一个：如果你说的是可计算实数，根据Church's theis,不管你用什么理论
来定义可计算性，不管你用什么程序语言，什么样的计算机，定义出来的可计算实数集
是一定的。一个数要么是可计算，要么是不可计算。 |
|
n********g
发帖数: 6504 | 49 傅立叶那时候还没有认识到可数这个概念。
描述任意对象（函数）这个理想很快就被发现局限，然后才衍生出可数不可数。
然后发现更简单基于整数而不需要实数的通用模型，这就是图灵机。
以后的发展就是可计算性概念和复杂性概念。 |
|
F**D
发帖数: 6472 | 50 【 以下文字转载自 Physics 讨论区 】
发信人: wonderlich (左岸，遁去), 信区: Physics
标 题: 中科院物理博士，某校副教授，离职报告（转）
发信站: BBS 未名空间站 (Sat Oct 23 16:47:11 2010, 美东)
离职报告
尊敬的领导：
你们好！
2006年8月，我一手拎着席子，一手抱着被子到学校来报到，工作。在办公室地板上睡
了3个晚上后，在XXX街XX坊和别人合租了一间房子，每月800元。自己感觉还好。但是
，当我的妻子到上海来看我的时候，却大哭了一场。她没有料到这个能写优美散文，中
英文俱佳，十年前的月薪就有3千元的男人却如此落魄：房间里没有像样的可以工作的
桌子，没有坐的地方，只能坐在床上；办公室也没有她可以坐的地方。是的，到现在，
我的办公室也只有一把椅子，一台普通的惠普激光打印机还是妻子送给我的生日礼物。
在妻子的坚持下，2007年3月，和别人合租大半年后，我搬到了XX新村X舍X号X室（证明
人：上XXXX学院XXX），月租金1600元。
我到学校来的唯一任务是做科研。不上课，也不带学生。我做的专业是理论物理。在我
看... 阅读全帖 |
|
