新书推介:《语义网技术体系》
作者:瞿裕忠,胡伟,程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
  •   Add to Google

    >> It is the theory that decides what can be observed. - Albert Einstein
    [返回] 中文XML论坛 - 专业的XML技术讨论区计算机理论与工程『 理论计算机科学 』 → 数理逻辑大师们[转帖] 查看新帖用户列表

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 60199 个阅读者浏览上一篇主题  刷新本主题   平板显示贴子 浏览下一篇主题
     * 贴子主题: 数理逻辑大师们[转帖] 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     chzhuang 帅哥哟,离线,有人找我吗?
      
      
      等级:大三(研究MFC有点眉目了!)
      文章:33
      积分:671
      门派:XML.ORG.CN
      注册:2006/2/13

    姓名:(无权查看)
    城市:(无权查看)
    院校:(无权查看)
    给chzhuang发送一个短消息 把chzhuang加入好友 查看chzhuang的个人资料 搜索chzhuang在『 理论计算机科学 』的所有贴子 引用回复这个贴子 回复这个贴子 查看chzhuang的博客楼主
    发贴心情 

    邱奇-图灵论题
    邱奇-图灵论题(The Church-Turing thesis)是计算机科学中以数学家阿隆佐•邱奇(Alonzo Church)和阿兰•图灵命名的论题。该论题最基本的观点表明,所有计算或算法都可以由一台图灵机来执行。以任何常规编程语言编写的计算机程序都可以翻译成一台图灵机,反之任何一台图灵机也都可以翻译成大部分编程语言程序,所以该论题和以下说法等价:常规的编程语言可以足够有效的来表达任何算法。该论题被普遍假定为真,也被称为邱奇论题或邱奇猜想 和图灵论题。
    目录
    • 1 本论题之等价形式
    • 2 本论题之起源
    • 3 本论题之成功
    • 4 哲学内涵
    • 5 补充材料
    • 6 参考文献

    本论题之等价形式
    本论题的另外一种说法就是逻辑和数学中的有效或机械方法可由图灵机来表示。通常我们假定这些方法必须满足以下的要求:
    1. 一个方法由有限多简单和精确的指令组成,这些指令可由有限多的符号来描述。
    2. 该方法总会在有限的步骤内产生出一个结果。
    3. 基本上人可以仅用纸张和铅笔来执行。
    4. 该方法的执行不需人类的智慧来理解和执行这些指令。
    此类方法的一个范例便是用于确定两个自然数的最大公约数的欧基里德算法。
    “有效方法”这个想法在直觉上是清楚的,但却没有在形式上加以定义,因为什么是“一个简单而精确的指令”和什么是“执行这些指令所需的智力”这两个问题并没有明确的答案。 (如需欧几里得算法之外的范例,请参见数论中的有效结果。)
    本论题之起源
    在他1936年的论文“论可计算数字,及其在判定性问题(Entscheidungsproblem--德语,译者注)中的应用”中,阿兰•图灵试图通过引入图灵机来形式地展示这一想法。在此篇论文中,他证明了“判定性问题”是无法解决的。几个月之前,阿隆佐•邱奇在“关于判定性问题的解释”(A Note on the Entscheidungsproblem)一文中证明出了一个相似的论题,但他采用但是递归函数和Lambda可定义函数来形式地描述有效可计算性。Lambda可定义函数由阿隆佐•邱奇和史蒂芬•克林(Stephen Kleene) (Church 1932, 1936a, 1941, Kleene 1935)提出,而递归函数由库尔特•歌德尔(Kurt Gödel)和雅克斯•赫尔不兰特(Jacques Herbrand) (Gödel 1934, Herbrand 1932)提出。这两个机制描述的是同一集合的函数,正如邱奇和克林(Church 1936a, Kleene 1936)所展示的正整数函数那样。在听说了邱奇的建议后,图灵很快就证明了他的图灵机实际上描述的是同一集合的函数(Turing 1936, 263ff).y
    本论题之成功
    之后用于描述有效计算的许多其他机制也被提了出来,比如寄存器机器(register machine), 埃米尔•波斯特(Emill Post)的波斯特体系,组合可定义性(combinatory definability)以及马尔可夫算法(Markov 1960)等。所有这些体系都已被证明在计算上和图灵机拥有基本相同的能;类似的系统被称为图灵完全。因为所有这些不同的试图描述算法的努力都导致了等价的结果,所以现在普遍认为邱奇-图灵论题是正确的。但是,该论题不具有数学定理一般的地位,也无法被证明;如果能有一个方法能被普遍接受为一个有效的算法但却无法在图灵机上允许,则该论题也是可以被驳斥的。
    在20世纪初期,数学家们经常使用一种非正式的说法即可有效计算,所以为这个概念寻找一个好的形式描述也是十分重要的。当代的数学家们则使用图灵可计算(或简写为可计算)这一定义良好的概念。由于这个没有定义的用语在使用中已经淡去,所以如何定义它的问题几经不是那么重要了。
    哲学内涵
    邱奇-图灵论题对于心智哲学(philosophy of mind)有很多寓意。有很多重要而悬而未决的问题也涵盖了邱奇-图灵论题和物理学之间的关系,还有超计算性(hypercomputation)的可能性。应用到物理学上,该论题有很多可能的意义:
    1. 宇宙是一台图灵机(由此,在物理上对非递归函数的计算是不可能的)。此被定义为大邱奇-图灵论题。
    2. 宇宙不是一台图灵机(也就是说,物理的定律不是图灵可计算的),但是不可计算的物理事件却不能阻碍我们来创建 超计算机(hypercomputer)。比如,一个物理上实数作为可计算实数的宇宙就可以被划为此类。
    3. 宇宙是一台超计算机, 因为建造物理设备来控制这一特征并来计算非递归函数是可能的。比如,一个悬而未决的问题是量子力学的的事件是图灵可计算的,尽管我们已经证明了任何由qubit所构成的系统都是(最佳)图灵完全的。约翰•卢卡斯(和罗格•本罗泽(Roger Penrose)曾经建议说人的心灵可能是量子超计算的结果。
    实际上在这三类之外或其中还有许多其他的技术上的可能性,但这三类只是为了阐述这一概念。
    补充材料
    • Hofstadter, Douglas R., Gödel, Escher, Bach: an Eternal Golden Braid, Chapter 17.
    参考文献
    • Church, A., 1932, "A set of Postulates for the Foundation of Logic", Annals of Mathematics, second series, 33, 346-366.
    • Church, A., 1936, "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics, 58, 345-363.
    • Church, A., 1936, "A Note on the Entscheidungsproblem", Journal of Symbolic Logic, 1, 40-41.
    • Church, A., 1941, The Calculi of Lambda-Conversion, Princeton: Princeton University Press.
    • Gödel, K., 1934, "On Undecidable Propositions of Formal Mathematical Systems", lecture notes taken by Kleene and Rosser at the Institute for Advanced Study, reprinted in Davis, M. (ed.) 1965, The Undecidable, New York: Raven.
    • Herbrand, J., 1932, "Sur la non-contradiction de l'arithmetique", Journal fur die reine und angewandte Mathematik, 166, 1-8.
    • Kleene, S.C., 1935, "A Theory of Positive Integers in Formal Logic", American Journal of Mathematics, 57, 153-173, 219-244.
    • Kleene, S.C., 1936, "Lambda-Definability and Recursiveness", Duke Mathematical Journal 2, 340-353.
    • Markov, A.A., 1960, "The Theory of Algorithms", American Mathematical Society Translations, series 2, 15, 1-14.
    • 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.
    • Pour-El, M.B. & Richards, J.I., 1989, Computability in Analysis and Physics, Springer Verlag.

    ----------------------------------------------
    觉之道:http://www.unicornblog.cn/user1/20/index.html

    点击查看用户来源及管理<br>发贴IP:*.*.*.* 2006/4/18 15:23:00
     
     GoogleAdSense
      
      
      等级:大一新生
      文章:1
      积分:50
      门派:无门无派
      院校:未填写
      注册:2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 理论计算机科学 』的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2022/12/4 11:16:52

    本主题贴数15,分页: [1] [2]

     *树形目录 (最近20个回帖) 顶端 
    主题:  数理逻辑大师们[转帖](19685字) - chzhuang,2006年4月18日
        回复:  好高兴自己开始学数量逻辑了,真希望以后做出点成绩来。(52字) - Kysio,2010年1月11日
        回复:  相当不错(10字) - xixi8356,2006年5月29日
        回复:  谢谢yang兄指正:1、他们两位相对没这么大吧,但在目前来说,他们参与的基于逻辑的人工智能,和基..(641字) - chzhuang,2006年4月19日
        回复:  ?[align=right][color=#000066][此贴子已经被作者于2006-4-19..(91字) - yangfeather,2006年4月19日
            回复:  这个跟个人兴趣和视野有关呀,不可能面面俱到。HILBERT当然称得上数理逻辑大学了,他提出问题,哥..(273字) - chzhuang,2006年4月19日
        回复:  不错!!!(10字) - amny,2006年4月18日
        回复:  Rule of Simplicity (by C.A.R. Hoare) - - ..(11868字) - chzhuang,2006年4月18日
        回复:  约翰.麦卡锡 --"人工智能之父"和LISP语言的发明人 1971年的图灵奖授予提出"人..(9704字) - chzhuang,2006年4月18日
        回复:  呵呵,顺序放错了,这个要放最前面,按时间顺序。莱布尼兹出生于书香门第的莱布尼兹是德国一位博学多..(3125字) - chzhuang,2006年4月18日
        回复:  阿伦·图灵 作者:liny信息来源:XY Studio编辑:EmilMatthew 更新时间..(4969字) - chzhuang,2006年4月18日
        回复:  邱奇-图灵论题邱奇-图灵论题(The Church-Turing thesis)是计算机科学中以..(5371字) - chzhuang,2006年4月18日
        回复:  哥德尔中国科学院软件研究所 张锦文 作者:张锦文 文章来源:中数网 点击数: 601 ..(22979字) - chzhuang,2006年4月18日
        回复:  ●希尔伯特,D.(Hilbert,David,1862~1943) 希尔伯特,D.(..(7208字) - chzhuang,2006年4月18日
            回复:  作者区分数理逻辑的标准是什么哪?好几位大师都没有提到,Hilbert是否可以称为数理逻辑大师?他的..(140字) - chinake,2006年4月19日

    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    70.313ms