x****u
发帖数: 44466 | 1 图灵机没错，但是是非确定图灵机的变体，不是一般意义的确定图灵机
除非有理论依据把所有随机都去掉才行 |
|
l*****8
发帖数: 16949 | 2 楼主的直觉是对的，但表述不够精确。
广义的说，所谓可以写出的无理数，就是你用有限个符号（允许用除了数字和英语字母
之外的符号，比如pi)表示出来，比如 pi, sqrt(2), e, e*pi， x^3-2x+100的最小根
等等等等。因为符号个数有限，可以很容易证明这样的字符串时可数多个，所以和有理
数一样多。
还有一种更加精确的定义，被称作可计算实数。也就是说存在一个图灵机，这个图灵机
可计算一个实数序列，这个实数是这个序列的极限。比如任何代数数，pi, e之类都是
这样的数（理论上pi,e，都能被计算到任意精确）我们能表述出来的实际就是这类“可
计算实数”。因为图灵机是可数的，所以这样的数字也是可数的。 |
|
h****g
发帖数: 56 | 3
是的
图灵机可从不考虑什么时间片的问题, 所谓计算的能力是指能
不能识别某类语言, 不存在误差的概念. 假如你考虑计算步数
的话, 用单带图灵机模拟多带图灵机当然要慢. 但从可计算性
角度看是一样的. |
|
d******p
发帖数: 24 | 4 用计算机科学解释比较容易理解。我们知道图灵机的停机问题
（就是判断一个程序能否在有限时间终止的问题）是不可解的。
就是说存在有可以停机的图灵机，但是我们无法证明。
一般的说，一个谓词逻辑命题对应两个集合，一个是使它为真的
元素组成的集合，另一个反之。那么有三种情况，1）两者都可以
判定，2）只有其中一个可以判定，3）都不能判定。第三种就是
不可解问题，就是不可以证明的问题,图灵机的停机问题就属于这类问题
当年图灵的一个重要工作方面，就是可计算问题 |
|
n**********5
发帖数: 1707 | 5 MIT的paper我基本不看。你知道库克是谁吧。我好歹还和他的学生扯过蛋。我估计我说
的名词你半个都没看懂。Probabilistic图灵机就是在扯蛋。说起P versus NP扯量子力
学的paper压根就不会有人review。写这些paper的人连图灵机是啥怕都没有弄懂。
课吧 |
|
n**********5
发帖数: 1707 | 6 惠普有这样的大牛还用裁员？他那篇文章没有一个大牛愿意给他review。倒是便宜了不
少PhD发refutation：那篇没有发表的文章有系统性不可修复的错误/
P versus NP的核心并不是什么算法复杂性。所有通过一个NP（完全）问题存在或不存
在P的算法都是死路一条。所以理论界说要有新思路。如果从算法入手这个问题能解决
，几十年前库克就解决了，前些年库克两年才要带一次课，就是不想打搅他思考，还用
等到现在的徒子徒孙？
99.99%的计算机系毕业生不知道NP是什么。为什么不相等？
图灵并没有得图灵奖。
不要以为去维基百科或者谷歌搜素一下就可以充专家。发言之前先问一问自己，你知道
怎么用确定性图灵机模拟不确定性图灵机么？这就是你修算法课或离散数学课知道图灵
机的缺陷。你要是不懂去谷歌个答案出来，你看得懂哪个答案么？ |
|
发帖数: 1 | 7 CS包含很多东西。搞理论的其实也是特边缘混不到饭吃。
至于理论并不十分依赖如何实现。理论上，动员全宇宙的力量也比不上一简单的图灵机
。因为图灵机是可数无穷的。但宇宙并不是无穷的。
如果是完全屏蔽只用光缆与外界沟通，电磁脉冲并不能歇菜计算机。
其实计算机不是一个问题。问题是谁掌握计算机。总有crazy scientist认为人类太多
罪恶，要建设新的美好伊甸园。
一个／群科学家制造一台智能毁灭人类的机器本质上和一个／群科学家制造毁灭人类的
超级炸弹没有区别。这一点上智能机器可能还好一点。 |
|
c****3
发帖数: 10787 | 8 评价图灵机没啥不对的，计算机行业本来也不是自然科学，没有方向问题，只是当时硬
件技术不成熟而已。
计算机软件就是靠应用驱动的，有没有图灵机其实无所谓。硬件技术成熟才是制约因素。
到最后都是有用户需求放在那里，看你去不去赚钱，你不去赚钱，还有其他人干。
人家囫囵吞枣，做个破烂出来，也能满足用户需求，赚大钱，最典型的就是微软的DOS
起家史 |
|
h*h
发帖数: 27852 | 9 【 以下文字转载自 Programming 讨论区 】
发信人: hsh (nidaye), 信区: Programming
标 题: 计算机行业拜图灵为鼻祖是为了自己高大上
发信站: BBS 未名空间站 (Fri May 20 22:34:32 2016, 美东)
图灵机看着很厉害的样子，但是计算机行业的发展和图灵机一分钱的关系也没有
其实计算机是机械计算尺的现代化，就是工程，真没有必要给自己拉个数学模型。现在
计算机系的教授们做的东西基本属于数学，应该让那些东西回到数学系，计算机系的教
授就应该搞工程方向的研究。
王垠工程的东西做得不错。他不是学数学的料，也不想搞数学，所以会郁闷，拿不到博
士 |
|
发帖数: 1 | 10 这拜数神教的思想比图灵机早。图灵这是教友而已。我最近突发灵感把图灵机拆开重装
。哈哈大笑。果然是比他老师的丘奇运算更有说服力。而且递归、枚举这些词突然有了
意义。我估计现在写教科书的人都没想到图灵是怎么设计图灵机的。所以也压根不理解
这些词。只变成了我教咒语。一代传一代。留待武学奇才能够从蝌蚪文中悟出绝学。
BTW：不要小看美帝的年轻人。弯曲高中生也有疯子钻研得很深。 |
|
w*********g
发帖数: 30882 | 11
为了提高集成度，晶体管越做越小，当小到只有一个电子时，量子效应就会出现。电子
将不再受欧姆定律管辖，由于它有隧道效应，本来无法穿过的壁垒也穿过去了，所以量
子效应会阻碍信息技术继续按照摩尔定律发展。
这两个限制就是物理学家们预言摩尔定律会终结的理由所在。
隧道效应：
由微观粒子波动性所确定的量子效应，又称势垒贯穿。本质上是量子跃迁，粒子迅
速穿越势垒。在势垒一边平动的粒子，当动能小于势垒高度时，按照经典力学，粒子是
不可能越过势垒的；而对于微观粒子，量子力学却证明它仍有一定的概率贯穿势垒，实
际也正是如此，这种现象称为隧道效应。
虽然这个预言在当时没有任何影响力，但“杞人忧天”的物理学家们并不“死心”
，继续研究，提出了第二个问题：
如果摩尔定律终结，在后摩尔时代，提高运算速度的途径是什么？
这就导致了量子计算概念的诞生。
量子计算所遵从的薛定谔方程是可逆的，不会出现非可逆操作，所以耗能很小；而
量子效应正是提高量子计算并行运算能力的物理基础。
甲之砒霜，乙之蜜糖。对于电子计算机来说是障碍的量子效应，对于量子计算机来
说，反而成为了资源。
量子计算的概念最早是1982年由美国物理学家... 阅读全帖 |
|
n********g
发帖数: 6504 | 12 钱学森是搞力学的。我觉得他未必懂热机过程和生物过程之间的可能关系。
就像90%的计算机博士未必知道图灵机。能够认识到图灵机也是一种热机的就更少之又
少。我怕全世界都没有多少千人想得到这一点。
不过钱学森作为代表接受过美国最高水平科学教育的人物发表这么一篇文章的破坏力是
惊人的。要承担一部分责任也不为过。 |
|
n********g
发帖数: 6504 | 13 他们的方法有一个很大的问题。没有能够证明能力强于图灵机。事实上，很有可能有未
知机制（退相干）阻止量子计算超越图灵机。假如相当于一亿亿次浮点计算能模拟，但
你只能算几十微秒就没有以后了。总计算能力有什么用。
而且是量子节点越多，退相干越快。 |
|
s***h
发帖数: 487 | 14 其实康托也是初等数学的专家，这哥们从初等数学的有限集合上的 Cantor diagonal
argument，扩展成同时存在的两个时间轴/时间之箭上的无限，去研究高等数学里的如
何把实数集定义弄完善的问题，结果被同时存在的两个时间轴/时间之箭搞疯了。
其实初等数学工作者都知道，所谓实数，其实就是 "几何可测量数" 的官话
。。。
这个在分数问题不大 。。。
在根号数和代数无理数时，因为勾股定理的存在，可以这个几何可测量数，由有限个符
号的图灵机算法，在有限次运算后，产生 。。。 虽然换成小数后的数位无线长还不循
环 。。。
然后就是超越数比如圆周率，跟以上一样，只不过那个图灵机要做无限次运算逼近收敛
，也就是加一个牛鼻顿的极限概念。
但问题是还有不可计算数，也就是生成之的图灵机算法本身有无限个符号 。。。 这样
同时出现两个不同方向的时间轴/时间之箭 。。。 于是康托就疯了 。。。 |
|
s***h
发帖数: 487 | 15 我看了一下 wiki 。。。 我很负责的说，古希腊人的分数 proof 是对的，而且也可以
用现代图灵机建立生成规则，转化成图灵机停机判断问题而严格化。
至于 wiki 里说的数学家不认可那个，是因为数学家是指纯数学，for its own sake，
可以没有任何实际用处，仅仅为数学美而存在 。。。 一大堆纯数学悖论说明了这点
。。。 总之如果要数学的证明实际有用，那么证明的思想师从古希腊人和欧几里德即
可，最多通过图灵机停机判断问题严格化就行了。 |
|
n********g
发帖数: 6504 | 16 以后有机会吧。我最近把图灵机拆了又装，挺有意思的。你搞生物不需要图灵机，会数
手指头整数就够用了。
样。 |
|
n********g
发帖数: 6504 | 17 不要啥觉得复杂的东西都往NP里塞。
不确定图灵机对应的是存在性问题。确定图灵机对应的是构造性问题。
所谓说不zuo不die。如女人说no男人该如何理解就是NP问题。存在一个（她认为）简单
的解；但要构造出一个能解出来的男人可能性则随着no的东西多了指数递减。 |
|
A***g
发帖数: 1816 | 18 我记得看过文章，量子计算机到目前为止的理论都是不能突破图灵机的范畴，也就是更
高更快更强，但是图灵机做不了的事量子机同样做不到。 |
|
n********g
发帖数: 6504 | 19 我去看的时候，那篇文章已经有几百个阅读了。
用不恰当的比喻，我的理解，作者的方法和求极限的方法很像。
举例说，如果P(n,k)表示确定图灵机能够在O(n^k)内解决的NP问题数量，NP(n,k)表示
不确定图灵机在O(n^k)内解决的NP问题数量。lim_{ntoinfity ktoinfity} P(n,k)/NP(
n,k) = ?。
如果P=NP，那么上述式子等于1。如果P!=NP，上述式子小于1。实际上考虑到这是无穷
问题，如果P!=NP，上述式子等于0。
作者构建一个P的超集P'，证明P<=NP<=P'，然后证明P=P'。夹逼定理，夹到相等。
另外，作者一个思路和洛必达法则很像，通过可以无穷次降次/微分将求极限问题。lim
_{ntoinfity ktoinfity} P(n,k)/NP(n,k) = lim_{ntoinfity ktoinfity} (P(n,k + 1
) - P(n,k))/(NP(n,k + 1) - P(n,k))...
这只是我的理解。文章里完全没有用到极限的概念。不过如果方法不被同意，同样涉及
无限的微积分也垮台了。 |
|
m**********e
发帖数: 12525 | 20 计算机里面涉及的是"数"的表示,
而其他科学里面涉及的是数本身,并不涉及表示论
比如,数学里面出现的pi,并不纠结pi究竟怎么写出来,大家都是用pi这个符号来代替
但是计算机里面就不一样了,因为目前计算机只能做数字操作,并不能进行逻辑推理,所
以pi必须用近似表示,才能继续运算
牛和娘这个智商,以为图灵机受限于数的特定表示,就企图否定其他学科里面也只能用某
些可以用图灵机来处理的数 |
|
n********g
发帖数: 6504 | 21 可计算数不限于图灵机。用图灵机只是一种信仰，二位一体。等价于耶稣就是上帝，上
帝就是耶稣。
我不研究可计算数。定义抄维基就没意思了。王垠可能了解更多。
我的感觉是如果用实数代替可计算数，可能有匪夷所思的事情发生。日常区别虽然不严
格，但数学上的R，实际含义指的是可计算数，不包括不可计算数。
不少现在的炼金术士，可能会在这上面栽跟斗。 |
|
s***h
发帖数: 487 | 22 你这个贴没看到本质问题。这个本质问题就是实数集上的 Axiom of choice，我这不是
开无轨电车，我这么解释。
你上面已经提到了 映射。 你这里的拓扑映射就是实数集合上面的 bijection 。整个
拓扑学就是硬射函数是连续函数， continuous transformation function。
但你不管是怎样的硬射函数，看起来多么 definable，你最终要走到两个实数集之间的
硬射，也就是定义域实数集和值域实数集之间的硬射。
而两个实数集之间的硬射，归根到底就是 axiom of choice 。 而实数集之间的 axiom
of choice ，是没有 definable 的（图灵机刹得住车的）choice function。这就带
来了到底是硬射美胸系花，还是硬射美腿系花，这样的硬射选择困难，因为 choice
function is non-definable（图灵机刹不住车，硬而不射），而最终让数学成为哲学
，或者说，美学。
哥们侃问题要侃本质 。。。
: 复球面无穷远点开集的定义，一句话就定义完了。但是其意义要慢慢展开
，因为
包含的
... 阅读全帖 |
|
n********g
发帖数: 6504 | 23 绕过第一个坑回到原点。比较两个无穷集合，人类唯一的方法就是一一对应，也就是双
手合十，看哪只手有没有多出的手指头。如果没有，就定义为相等，否则就是不相等。
对角线是找到/构造这个不相等（多出手指头）的一个方法。康托尔用它证明实数集比
整数集大。哥德尔用它证明不完备。图灵用它证明判定问题无解。也有人想用它构造NP
中不能被P解决的问题。You know what，还没找到。
到了这里，证明不等的已经黔驴技穷。让我们看看证明相等的怎么样。
由于机器的不同（距离太远/无穷远手不够长），直接双手合十行不通（否则问题也就
不拖到今天了）。和库克的思路类似但作用相反，（可数）无限只手怎么样？也就是说
，我知道我的左手和右手手指是一一对应的。如果有可数无限个这样的人的右手合下一
个人的左手，跨越时空，一直下去到宇宙的尽头把牛郎和织女连起来，能否找到多出的
手指头或都是一一对应的。
数学地说，如果我们定义一个测度，把NP分成子类/集，记为P属于等于NP/0属于等于..
.属于等于NP/i...属于等于NP。如果P等于NP，则无论任何测度（如全男人测或全女人
测），这个式子都必然处处取等号。如果P不等于... 阅读全帖 |
|
n********g
发帖数: 6504 | 24 P和NP是两个语言的类。是所有图灵机能接收(accept)语言的子类（满足图灵机类型及
时间限制）。
语言就是一个图灵机能接收的输入符号串的集合（所以所有符号串都是停机的）。通常
一个图灵机m能接受的语言记为L(m)。
定义一个语言的函数（测度），f(L(m))，NP/i这个记号在这里定义为属于NP的的子集{
L(m) in NP : f(L(m))<=i}。 |
|
n********g
发帖数: 6504 | 25 这些问题、输入、语言的定义在计算复杂性中不重要。
因为计算复杂性不讨论为什么图灵机重要有用，或P=NP如何改变世界。
只就事论事讨论某种图灵机处理问题需要的资源（复杂性）。
P |
|
n********g
发帖数: 6504 | 26 EE学的是大专、中专水平的CS。图灵机、状态自动机、图灵机语言、如何简化等等不花
时间去玩基础就是不行。 |
|
n********g
发帖数: 6504 | 27 俺以前也很谦虚的。人的自信还是得靠一次一次打大boss通关才能升级。
俺靠图灵机骗到TA教图灵机的弯曲贫困线羊和牛跪舔。靠各层次语言唬到大藤女CS解衣
服扣子。
茴香豆俺研究N十年了。没人知道俺还藏着啥。最好不要和俺讨论CS。
还是讨论雅利安吧。 |
|
a****o
发帖数: 6612 | 28 硅基芯片的电脑，其原理是图灵机。Alpha GO是基于图灵机的，已经击败了人类棋手。
人工智能已经超越人类了。
“事实上现在研究中电脑也只是当成计算器来用的”
我不知道你是怎么区分开电脑和计算器的。在我看来，计算器和电脑在原理上并没有本
质的不同，后者速度更快，内存更大，计算功能更强大。 |
|
发帖数: 1 | 29 对我来说也没什么区别。
靠的都是运算速度快，记忆能力强，当然速度有强弱之分。
但做数学的习惯无视速度。
: 硅基芯片的电脑，其原理是图灵机。Alpha GO是基于图灵机的，已经击败了人类
棋手。
: 人工智能已经超越人类了。
: “事实上现在研究中电脑也只是当成计算器来用的”
: 我不知道你是怎么区分开电脑和计算器的。在我看来，计算器和电脑在原理上并
没有本
: 质的不同，后者速度更快，内存更大，计算功能更强大。
|
|
g*******y
发帖数: 1930 | 30 正因为这样，所以如果大数分解是NPC，那么就证明了量子计算体系是对经典计算模型
的质的超越。
可惜目前已知的量子算法，最多都只能解决某些NP的问题。
我没有听说过有其他的计算模型。不知道我记对了没，貌似所有经典(物理意义上的“
经典”:非量子的)的计算模型，都能由图灵机/随机的图灵机等价。
Non |
|
j*d
发帖数: 96 | 31 1. 超图灵机的模型早就有人想过了, 只是受到物理的限制造不出来而已。
2. 非确定性图灵机和确定性图灵机计算能力相同。 |
|
t******l
发帖数: 10908 | 32 从符号系统上说，我民科觉得在基本的 集合论 / 高中代数解析几何 / 大一微积分-
泰勒-拉普拉斯等等之后，现代数学和现代马工学彻底分道扬镳了。
而这个分道扬镳的最重要的促生因子，我民科认为，概念层次上是图灵机，实现层次上
是超大规模集成电路。具体如下：
数学/物理要往前发展，这符号系统就得支持一层加一层的抽象。不仅如此，
牛顿都要站在前人的肩膀上，这符号系统也得一代一代的继承。
而现代数学，采取了一个大伙儿看起来不明觉厉的艰深办法，但简单而言，就两个
字：“造新字！”。其实这是因为原始人没有灵活可重组的句法文法结构，有个新事
儿，唯一的办法，就是造一个新字。
其实跟古猿不会阿拉伯数字，只会在木头上一道一道的往上刻刀痕，一德行。
现在放眼望去，是不是满树林都是谁的刀痕在飞？
但后来出现了图灵机。 |
|
h*****m
发帖数: 1034 | 33 这个对计算机如何证明数学定理实在是不懂。
目前看来，人类有一特点，就是会联想，有时风马牛不相及的事情也能给你瞎联系到一
起，可能就是神经短路的结果，但恰恰有时就是解决问题的关键。
另一特点是好奇，偶尔发现个什么就想总结出个规律来。大言不惭地说，我这次看到循
环小数的循环节乘以被除数等于999。。放两千年前（两千年前已经有一批数学家了？
那就五千年前吧），是不是也能整出个啥啥猜想一类的？计算机有没有这种好奇心？
至于阿发猫，首先，它会不会提出问题？貌似现在计算机都是有一定目标去完成的。就
解决问题来说，在已有成功先例的情况下，照猫画虎构造个什么来解决与已经解决的问
题类似的问题可能还行，也就是说有一定套路的解法。创造性地提出个什么理论，估计
还是不成。
更深一点说，人脑是不是图灵机？和图灵机之间有没有本质的区别？有没有不可逾越的
鸿沟？
），
combinatorics
而 “reverse math modelling” / “math model invention”，是反过来，海阔
天空吃饱了撑的瞎几把乱想一个 “space-time-pattern math model”，然后... 阅读全帖 |
|
B********e
发帖数: 10014 | 34 哈哈，不是，前一阵子我们家小相声演员文siri我乖吗？
siri如图回答。
让我有所思考。刚才觉得可能有点不符合这里的味道就删了。
我倒是看过图灵机理论，但觉得不足以讲好这个东西。
你这些问题的答案其实不在答案，而在问题本身。
完全定义了你的问题之后，才好讨论答案。比如什么是非图灵机，什么是百分百模拟。
说实话，我不懂，甚至没有弄懂的兴趣。
我已经老的对太多的事情提不起兴趣了hoho |
|
L*****e
发帖数: 8347 | 35 “这就是沟代尔所想说的？”小白不明白这为啥值得一个顶尖数学家投入那么大的精力。
“当然不是，关键的是沟代尔推论出：如果一串符号所表达的函数最后表达的是自己本
身，那么这个函数的表达正确与否则可能是不可证明的。这是一个相当让人错愕的结论
，因为它和希尔伯特和很多其他人所以为的结果相反。”
“希尔伯特，刚才说过希尔伯特了吗？”小白觉得这个名字似乎刚刚听到过。
“没有。”
“提到过，你刚才说希尔伯特等会儿再说，先说沟代尔。”鲁迪纠正道。
“这希尔伯特又是谁？”小白问。
“他呀，他是个喜欢问一堆艰深问题的家伙。”阿兰觉得这样回答小白的问题比告诉小
白希尔伯特长什么样要好得多，“有一次他一气问了23个问题，沟代尔回答出其中一个
。”
“图灵回答了另外一个问题。”鲁迪边说边暧昧地笑着。
“图灵又是谁？”
“呃。。。图灵是我。”阿兰对小白能记住自己的first name已经很满意了。
“啊！别吊我胃口，你回答的是什么问题？”
“一阶逻辑的判定问题。”
“啥是一阶逻辑判定？”
“希尔伯特想知道，对于任何给定的逻辑语句，是否可以判定其是真还是假。”
“沟代尔后来把这个问题改进了一下。”鲁迪指出。
“对，... 阅读全帖 |
|
t******n
发帖数: 2939 | 36 ☆─────────────────────────────────────☆
xiongyp (dreamrain) 于 (Fri May 24 08:41:56 2013, 美东) 提到:
我们假设不知道什么叫素数，我们对正整数集合进行如下的定义来定义素数。（这是从
链接上取下来的，也是I63的定义）
(1) 1不是素数 (base case)
(2) a是素数当且仅当a不能被任何小于它的素数整除。
我曾经多次指出，这个定义在用素数定义素数，是不正确的。但看到很多的反驳如下。
1不是素数, 我们考察2，发现小于2的素数集合为空集，于是2为素数。以此再往下递归
，得出所有素数的定义。我想昨天深入讨论此内容的人，都不会反对我的总结吧。关于
"小于2的素数集合为空集"推出"2为素数"，因我的不慎，还做出过郑重道歉。
好，我们仿造这种递归定义，来定义偶数。
我们假设不知道什么叫偶数，我们对非负整数集合进行如下的定义来定义偶数。
(1) 0不是偶数 (base case)
(2) a是偶数当且仅当a与任何小于它的偶数之差为2的倍数。
我从base case开始。0不是偶数。我们考察... 阅读全帖 |
|
t******l
发帖数: 10908 | 37 另外你的 “可计算实数”，是指现代数学概念内的 “可计算”。
而图灵机之后的马工学，如果是 computalism，那一切数字都 “可计算”。(当然还是
存在对于图灵机的 undecidable problem，但那不是数字)。 |
|
l*****8
发帖数: 16949 | 38 错了，这里说得可计算，就是图灵机可计算，不是用森马柯西之类定义的。但图灵机是
可数的，所以可计算实数的数量也是可数的。但实数的总数是不可数的，因此绝大多数
实数还是不可计算的。这个和Non-computable problem是两码事。 |
|
s******y
发帖数: 28562 | 39 上面有人贴的连接里已经有解答了。
在绝大部分情况下，图灵机能做的事情蓝布搭也能做。所以一般情况下大家认为这两者
功能差不多。但是特殊情况也有。有些功能是图灵机能实现而蓝布搭不能做的（连接里
举了一个例子）。
另外，图灵机的历史地位不是因为它多么的好用或者牛叉，而是因为它是现代计算机理
论的奠基者。蓝布搭计算一开始不是为了这种事情而设计的，但是后来被adapt 到那个
领域去了而且在大部分情况下比图灵机容易使用和理解。
图灵在计算机领域里的地位堪比达尔文在生物学里的地位。虽然达尔文的理论在现代生
物学看来是很不完善的，有些地方甚至是错的，但是这个不影响他作为现代生物学奠基
人的地位。
王某只从功能的强大或者易用与否来评价图灵机，其实是本末倒置。这个就好像说最早
之一（注意是之一）的可编程计算机ENIAC 的功能不如现代的iPhone 强大所以ENIAC就
是狗屎一样无聊和可笑。 |
|
s******y
发帖数: 28562 | 40 I think you completely missed the point.
我说的是王垠对图灵的评价可以看出他很肤浅，
你贴的是别人对图灵的评价，我不知道这个能说明什么问题。
王垠对图灵的评价里一个最重要的论点就是因为图灵机不容易
理解所以图灵是个烂人。这个就好像说因为微积分不如小学数学
容易理解所以微积分是没用的一样荒唐。
图灵的地位在于凡是能用图灵机模拟出来的函数（或者说功能）
都是可以用（某种）计算机计算的，所以成了现代计算机理论的
一个重要基础。至于说图灵发明了计算机？图灵自己可没有这么
说过，正经的搞计算机理论的人也没有这么说过，最多就是一些
无关的俗人自己揣摩出来给图灵乱贴金的，但是这笔账根本算不
到图灵或者计算机理论的头上好不好。所以说王垠根本就是竖错
了靶子放错了枪。但是他能说出这种话，尤其是考虑到他居然用
“是否容易理解”来作为评价图灵机器是否有用，让我觉得他
根本就没有搞懂一个体系的底层基础理论。
influences |
|
s******y
发帖数: 28562 | 41 那三篇文章说的和王垠说的根本就不是一回事吧。
第一篇说的是popular descriptions不够准确。注意针对的是“popular”（世俗人）
的一些传说搞错了。
第二篇是一篇科普文，说的是图灵并没有发明计算机（学术界也从来没有人说他发明了
计算机），也是针对世俗人的一些误会进行澄清。
第三篇相当于一个科技历史考察文，对图灵对计算机理论的贡献讲得很清楚，并把图灵
和高斯作比（我觉得这个比方非常的恰当）。
而王垠说的无非就是三件事情：
1。图灵机不如Lambda 计算好用，所以图灵是傻B；
2。计算机学领域里面那么多人居然都没有看出图灵机不如Lambda 计算好用，所以计算
机学领域里面的人全部都是傻B；
3。计算机学会(ACM)居然把他们的大奖用图灵而不用Lambda命名，所以他们是大傻B
所以我还真不觉得他说的有什么道理，俗话常说的半桶水乱晃，在他那里是连半桶水都
没有，就是一个空桶在那里乱敲。
至于我为什么趟这个混水，那是因为他（王）的文章贴得到处都是，想不看到都难。 |
|
l*********g
发帖数: 1899 | 42 你有没有认真消化过你贴出来的下面这2个links里的帖子？既然你认为那些帖子是真知
灼见。
你以下帖子里的第一个link里的5楼 digua说的内容在核心思想上和sunnyday说的是类
似的。大致意思就是王对于图灵机的根本用途和意义都没有搞清楚（例如居然把图灵机
和编程语言Lambda作比较）。
我认为不管programming版还是joke版还是哪个版，也没有那么多人觉得王招人恨，只
是觉得他可笑，看个笑话而已。 |
|
wy
发帖数: 14511 | 43 有了Turing Machine的概念，偶们就可以定义NP问题了，
P Class: 就是可以在多项式时间内用决定性图灵机解决的
问题的集合。
NP class: 可以在多项式时间内用非决定性图灵机解决的问题
的集合，比如说上例就属于NP集。
一个立即的推论就是P blongs to NP.
同学们广泛知道的计算机界最伟大的一个open problem就是：
Is P=NP?
一个定义：
1. NP-completeness(NP完全）:
一个问题（程序）A in NP,如果所有其它的NP问题
都可以在多项式时间内降解到A,那么我们说A是一个
NP完全问题。这个定义的说明实在太费事，不详细说了，
只说一下它的意义：就是如果我们能够发现一个解决
A的算法属于P,那么我们可以立即下结论说NP==P!
NP完全问题不象大家想象的那样少，相反，非常多，
比如3SAT问题，vertex cover problem,blahblah. |
|
a********e
发帖数: 16 | 44 四.艾兹赫尔·W·戴克斯彻（Edsger W. Dijkstra）。
1)理论物理学家转入计算机编程。
2)1956年左右，思考出最短路径算法，修改后为最短子分支树算法，发表于《数字数学
》。当时数学界几乎全在研究连续统和无穷大问题，无人关注。
3)针对资源共用问题，提出“互斥”方法，基于铁路信号系统的P（荷兰语“通过”）
、V（荷兰语“释放”）操作。
4)“哲学家的晚餐”，体现死锁问题。之后几年最成熟计算机系统MULTIX却并没有考虑
死锁问题。
5)前往美国布劳斯公司，推行编程的可验证性，提出“GOTO语句是有害的”，却阻碍了
一些程序员所喜欢的程序不确定性。
6)《程序与证明的形式开发》，拉近数学与计算机科学的距离。
7)对人工智能说不。
五.迈克尔·O·拉宾（Michael Oser Rabin）。
1)德国犹太人拉比家族（观察思考产生智慧的阶层）。
2)能够猜想的计算机：考虑有限状态机，证明非确定性有限状态机与确定性有限状态机
之间的转换关系。
2+)图灵于1935年定义“计算”的逻辑基础，设计图灵机。借助哥德尔不可判定原理，
设计停机问题，挑战希尔伯特判定性问题。
3)对计... 阅读全帖 |
|
r*******q
发帖数: 50 | 45 前几天我在这说可以用非常简单的方法解决内存泄漏的问题，很多人都不相信。
现在有几小时空闲，码几行字加以说明。首先声明以下讨论仅限C++。
首先我们把需求列一下：
1.管理一片内存或需要分配的资源，要求程序员可以完全只分配，不释放，系统
将自动在该内存或资源不再需要的时候释放。
2.程序员可以清楚地知道系统究竟在什么地方释放的资源。这样程序员就可以对
整个系统有完全的控制。
3.所使用的方法的书写复杂度与不用该方法时差不多。例如：用new/delete只写
2-3行的，用新方法最多3-4行。
4.在大多数C++编译器下面所使用的方法不能有歧义。
5.当管理内存时，可以把内存按数组访问，并且可以检测内存越界错误。同样程
序书写复杂度也不能增加。
我们再来看看C++语言本身的特性。设计C++的时候必须有一个计算机的模型，这
个模型中有的特性C++就必须支持，而没有的特性就不会出现在C++中。大多数程
序语言都是基于单带图灵机设计的，C++也不例外。在单带图灵机中，是没有线
程的概念的，所以C++也没有线程的概念。所以我们现在不考虑多线程的问题。
这并不意味着这里提出的方法无法 |
|
x****u
发帖数: 44466 | 46 FP的致命缺陷是，图灵机在现实中是不存在的。所以任何把计算能力发挥到极限的程序
，都不可以基于图灵机这个假设。 |
|
x****u
发帖数: 44466 | 47 因为CPU不是图灵机，而是在不考虑资源时可以和图灵机等价而已。
所以高性能程序不可避免的需要深度介入CPU的设计。
比如当年的极度回避多线程，和现在鼓励使用多线程的理想，都是现实的要求。 |
|
x****u
发帖数: 44466 | 48 来自主题: Programming版 - 王垠忏悔录 类似王垠那套关于FP语言和体系结构的想法，日本政府早在80年代就投入天文数字的经
费研究，然后在全球学术界面前失败了的。日本人搞出来的类似王垠成果的代码甚至机
器，在一地鸡毛后送给同行人家都不要。
某些小屁孩总是幻想有一个银弹，可以一下子解决所有体系结构或者AI的问题，银弹思
路在任何领域都是做梦。
我前面也说过，FP也许是图灵机的银弹，但可惜的是地球上只有近似图灵机，连停机问
题对这些机器都是可解的。 |
|
x****u
发帖数: 44466 | 49 基本就是这个答案。
就算计算机真的是图灵机，大部分计算机语言也不等价于图灵机。所以针对具体语言
分析，还是可以判定的。 |
|
g****t
发帖数: 31659 | 50 CS哪个课学图灵机? (或者哪个程序员对图灵机感兴趣。)
一般也都会学到Lambda Calculs,部分递归函数什么的。
计算理论本来就不是必修课。就跟图像处理，图形学，人工智能，这些都是专业方向，
不是CS本科必修课。
我打赌这版上大多数人都没学过图像处理和图形学，但我不会说什么学过图形学的秒杀
没学过的云云。
special
using |
|
