Talk:计算机科学
 |
条目质量提升计划 | |||
| 计算机科学条目质量已经提升，根据条目质量标准参考的评分，结果如下： | ||||
| 平均得分 | 1.9 | 条目质量 | 可 | |
Computer Science has nothing to do with so called “电子工程”. He who linked them together didn't know CS at all. ---happyevolving 2004.4.13
翻译质量比较差. 建议多看看中国大百科全书. 我今天帮忙修改了一下计算机科学的首页(后面有些没来得及修改). 建议到国内的大学计算机系,大的计算机业者论坛等多宣传. 这个工程很浩大,要靠更多人的力量做好了对中国学者很有好处. 做不好,也确实丢人(看看日本人做的就不错). --hwei21
- 所言极是。可以联系CSDN，在他们的首页上做些宣传。孤雁 17:28 2004年5月17日 (UTC)
像这类文章大可参考其他语言版本自行编撰， 不必处处以英文版为基准。 英文版虽然整体质量较高， 但欠准确、欠完善的文段也是随处可见。 别的我拿不准， 单说计算机和数学方面的文章中， 能找出的错误和不恰当措辞我就能找到好几处。 全文翻译之风需改！ --孤雁 17:28 2004年5月17日 (UTC)
本文先前被人惡意刪除開首的內容，煩請管理員代為復舊，將變更退回至上次 Aniu 站友的更改。謝謝! -- 石添小草 07:00 2003年12月19日 (UTC)
- 已经恢复，感谢您的提醒--Shizhao 07:09 2003年12月19日 (UTC)
-
- 不是管理员也可以恢复到以前的页面：Wikipedia:如何把页面恢复到早期版本。--Formulax 08:07 2003年12月19日 (UTC)
目录 |
[编辑] 有争议的说法
Church-Turing Thesis 不是一个定理 而仅仅是一个猜想，因而不能说他表明什么。 第二自然段需要重新组织一下。 --孤雁 17:37 2004年5月17日 (UTC)
我的看法，这只是个命题，因为对于什么是可计算的这个概念没有办法用数学方法严格定义。这里的可计算只是对人类计算能力直觉的一种描述。这个命题现在被大多数人接受，是因为尚无反例－没有找到一种大家公认不是可计算的函数不能用图灵机所计算。另外其它人试图对可计算做的定义如lambda演算，递归函数和图灵机都被严格的证明是等价的。这说明图灵机模型很有道理。但church-turing命题无法被证明，也谈不上是个数学意义上的猜想。肉丝跑蛋 00:07 2004年9月24日 (UTC)
第二自然段说：“现有的各种计算设备在计算的能力上是等同的”。 此说不准却，很多计算设备逻辑上等同于有穷自动机， 不能与其他类图灵机等同。 --孤雁 17:37 2004年5月17日 (UTC)
“图灵机”主要用于概念层面上的分析， 在应用领域，极少有复杂的机器直接构筑在图灵机模型上。 因而不能说“它们(图灵机)是许多实际机器的模型” --孤雁 17:37 2004年5月17日 (UTC)
“并行计算机”(非量子)实际上就是“并行图灵机”， 仍然是图灵机的自然延伸， 把它说成是“其他种类的机器”不太妥当。 至少应当在括号中指出这种联系。 --孤雁 17:37 2004年5月17日 (UTC)
[编辑] 译名
“Oracle”有“先知”的译法。 “Random”有“随机源”的译法。 --孤雁 17:39 2004年5月17日 (UTC)
[编辑] 我的一些意见
Oracle 翻译成“神谕”比较好，现在大部分教科书上都是如此翻译的。
另外，姚先生的主要贡献并非在“计算理论”方面，而是在“计算复杂性”和“伪随机数理论”方面。
对 Dijkstra 的名言的翻译我觉得不够准确，修改了一下，不过我对自己的翻译也不满意。谁能提出更好的翻译方法？
Church-Turing Thesis 的描述不准确。事实上，对于该命题比较恰当的叙述是：一切直觉上的可计算的概念，都等价于图灵机可计算的概念。或者换句话说，任何捕捉了直觉上可计算性的计算模型的计算能力都和图灵机等价。其实关于Church-Turing thesis 有很多误解，现在流行的这种叙述应该是 Church thesis 的一种扩展，Church 的原始表述其实是非常保守的。
Church 的原文是：Every effective computation can be carried out by a Turing machine. 这里的关键在于“effective computation” 到底是什么意思？
在文献[1]中，Church对“effective computation”的定义就是“lambda definable”：
define the notion ... of an effectively calculable function of positive integers by identifying it with the notion of a recursive function of positive integers (or of a lambda-definable function of positive integers). [1]
而Turing在[2]中则用Turing computable来解释“effective computation”：
LCMs [logical computing machines: Turing's expression for Turing machines] can do anything that could be described as "rule of thumb" or "purely mechanical" . ... This is sufficiently well established that it is now agreed amongst logicians that "calculable by means of an LCM" is the correct accurate rendering of such phrases. [2]
但是在Turing提出Turing Machine的论文[3]中，全文的第一句话是：
The "computable" numbers may be described briefly as the real numbers whose expressions as a decimal are calculable by finite means. [3]
第一段的最后一句话是：
According to my definition, a number is computable if its decimal can be written down by a machine. [3]
由此可见Turing认为computable就是可被一台机器计算（这里Turing并没有明确指出这台 机器必须是Turing Machine, TM在后文才提到）。
文章[3]的第一部分第四段的内容是：
In a recent paper Alonzo Church has introduced an idea of "effective calculability", which is equivalent to my "computability", but is very differently defined. Church also reachs similar conclusions about the Entscheidungsproblem. The proof of equivalence between "computability" and "effective calculability" is outlined in an appendix to the present paper. [3]
这说明Turing认为Church所说的"effective calculability"和他所定义的"computability" 是一回事。
[3]中还有更多的证据，但这里就不一一重复了。
总而言之，可以看出Turing对"computable"或"effective calculable"的定义主要有两种：
- can be computable (by a man with pencil and paper) in finite means.
- can be computable by a machine.
注意，这里Turing认为这两种说法是一回事，他大概认为任何机器能进行的计算都可以由 人通过有限的步骤来模拟执行，进而通过Turing Machine计算。
不过根据[4]中的解释，Turing喜欢把Turing Machine简称Machine，所以这个证据也并不 能说明Turing认为“一切机器可计算的都是Turing Machine可计算的”。
归根结底，我的结论是：Turing和Church根本没有给出"computable"或"effective calculable" 的精确定义。
在文献[4]中提到了Church-Turing Thesis的另外两种扩展：
Thesis M: Whatever can be calculated by a machine (working on finite data in a ccordance with a finite program of instructions) is Turing-machine-computable.
(Thesis M 在[5]中又被称为 Strong Church-Turing Thesis)
以及
Thesis S: Any process that can be given a mathematical description (or that is scientifically describable or scientifically explicable) can be simulated by a Turing machine.
按照[4]所言，Turing 和 Church 都没有明确地赞成或反对Thesis M和Thesis S，他们总 是采取比较保守和谨慎的态度，只谈论"effective calculable"的东西。
参考文献：
[1] Church, A. 1936，‘An Unsolvable Problem of Elementary Number Theory’. American Journal of Mathematics, 58, 345-363.
[2] Turing, A.M. 1969,‘Intelligent Machinery’. National Physical Laboratory Report. In Meltzer, B., Michie, D. (eds). Machine Intelligence 5. Edinburgh: Edinburgh University Press.
[3] Turing, A.M. 1936. On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, 42 (1936-37), pp.230-265. Available online at http://www.abelard.org/turpap2/tp2-ie.asp.
[4] http://plato.stanford.edu/entries/church-turing/
[5] http://en.wikipedia.org/wiki/Church-Turing_thesis
── Starfish 13:46 2004年6月30日 (UTC)
移动自Wikipedia:条目质量提升计划/票选主题
[编辑] 计算机科学
[编辑] 支持
[编辑] 评论
毕竟，一周七天泡在网上的，有不少都是搞计算机的。 3周的时间可以主要集中在一些最基础的理论和概念上。
结束移动 * 结束移动
希望能够同时完善category:计算机科学--百无一用是书生 (Talk) 03:35 2004年9月27日 (UTC)
[编辑] 条目体例
建议：1、加强指导性——计算机科学之下的学科很多，应该简述各下属学科的发展方向和最新重大进展，给阅读者一个整体概念；2、作为20世纪的重大发明，计算机科学的巨大影响应得到充分阐述
