徽标
联盟百科
通讯
下载应用,请到 Google Play
新! 在您的Android™设备上下载联盟百科!
安装
比浏览器更快的访问!
 

一阶逻辑和停机问题

快捷方式: 差异相似杰卡德相似系数参考

一阶逻辑和停机问题之间的区别

一阶逻辑 vs. 停机问题

一阶逻辑是使用於数学、哲学、语言学及電腦科學中的一种形式系统。 過去一百多年,一階邏輯出現過許多種名稱,包括:一阶斷言演算、低階斷言演算、量化理論或斷言逻辑(一個較不精確的用詞)。一階邏輯和命題邏輯的不同之處在於,一階邏輯有使用量化變數。一個一階邏輯,若具有由一系列量化變數、一個以上有意義的斷言字母及包含了有意義的斷言字母的純公理所組成的特定論域,即是一個一階理論。 一階邏輯和其他高階邏輯不同之處在於,高階邏輯的斷言可以有斷言或函數當做引數,且允許斷言量詞或函數量詞的(同時或不同時)存在。在一階邏輯中,斷言通常和集合相關連。在有意義的高階邏輯中,斷言則會被解釋為集合的集合。 存在許多對一階邏輯是可靠(所有可證的敘述皆為真)且完備(所有為真的敘述皆可證)的演繹系統。雖然一階邏輯的邏輯歸結只是半可判定性的,但還是有許多用於一階邏輯上的自動定理證明。一階邏輯也符合一些使其能通過證明論分析的元邏輯定理,如勒文海姆–斯科倫定理及緊緻性定理。 一階邏輯是數學基礎中很重要的一部份,因為它是公理系統的標準形式邏輯。許多常見的公理系統,如一階皮亞諾公理和包含策梅洛-弗蘭克爾集合論的公理化集合論等,都可以形式化成一階理論。然而,一階定理並沒有能力去完整描述及範疇性地建構如自然數或實數之類無限的概念。這些結構的公理系統可以由如二階邏輯之類更強的邏輯來取得。. 停机问题()是逻辑数学中可计算性理论的一个问题。通俗地说,停机问题就是判断任意一个程序是否能在有限的时间之内结束运行的问题。该问题等价于如下的判定问题:是否存在一个程序P,对于任意输入的程序w,能够判断w会在有限时间内结束或者死循环。 艾伦·图灵在1936年用對角論證法证明了,不存在解决停机问题的通用算法。这个证明的关键在于对计算机和程序的数学定义,这被称为图灵机。停机问题在图灵机上是不可判定问题。这是最早提出的决定性问题之一。 用数学语言描述,则其本质问题为: 给定一个图灵机T,和一个任意语言集合S,是否T会最终停机于每一个 s \in S。其意义相同于可确定语言。显然任意有限 S 是可判定性的,可数的(countable)S 也是可停机的。 停机问题包含了自我指涉,本质是一阶逻辑的不自洽性和不完备性,类似的命题有理发师悖论、全能悖论等。.

之间一阶逻辑和停机问题相似

一阶逻辑和停机问题有(在联盟百科)5共同点: 可判定性哥德尔不完备定理艾伦·图灵集合数理逻辑

可判定性

没有描述。

一阶逻辑和可判定性 · 停机问题和可判定性 · 查看更多 »

哥德尔不完备定理

在数理逻辑中,哥德尔不完备定理是库尔特·哥德尔于1931年证明并发表的两条定理。简单地说,第一条定理指出: 这是形式逻辑中的定理,容易被错误表述。有许多命题听起来很像是哥德尔不完备定理,但事实上并不是。具体实例见对哥德尔定理的误解 把第一条定理的证明过程在体系内部形式化后,哥德尔证明了第二条定理。该定理指出: 这个结果破坏了数学中一个称为希尔伯特计划的哲学企图。大卫·希尔伯特提出,像实分析那样较为复杂的体系的相容性,可以用较为简单的体系中的手段来证明。最终,全部数学的相容性都可以归结为基本算术的相容性。但哥德尔的第二条定理证明了基本算术的相容性不能在自身内部证明,因此当然就不能用来证明比它更强的系统的相容性了。.

一阶逻辑和哥德尔不完备定理 · 停机问题和哥德尔不完备定理 · 查看更多 »

艾伦·图灵

艾伦·麦席森·图灵,OBE,FRS(Alan Mathison Turing,又译阿兰·图灵,Turing也常翻譯成--林或者杜林,)是英国計算機科學家、数学家、邏輯學家、密码分析学家和理论生物学家,他被视为计算机科学與人工智慧之父。 在第二次世界大战期间,图灵曾在“政府密码学校”(GC&CS,今政府通信总部)工作。政府密码学校位于布萊切利園,是英国顶级机密情报机构。图灵在这里从事密码破译工作,有一段时间,他领导了(Hut 8)小组,负责德国海军密码分析。 期间他设计了一些加速破译德国密码的技术,包括改进波兰战前研制的机器,一种可以找到恩尼格玛密码机设置的机电机器。 图灵在破译截获的编码信息方面发挥了关键作用,使盟军能够在包括大西洋战役在内的许多重要交战中击败纳粹,并因此帮助赢得了战争。 图灵对于人工智能的发展有诸多贡献,例如图灵曾写过一篇名为《》的论文,提問「机器会思考吗?」(Can Machines Think?),作為一种用于判定机器是否具有智能的测试方法,即图灵测试。至今,每年都有试验的比赛。此外,图灵提出的著名的图灵机模型为现代计算机的逻辑工作方式奠定了基础。 图灵是著名的男同性恋者,并因为其性倾向而遭到当时的英国政府迫害,职业生涯尽毁。他亦患有花粉过敏症。 图灵还是一位世界级的长跑运动员。他的马拉松最好成绩是2小時46分03秒(手動計時),比1948年奥林匹克运动会金牌成绩慢11分钟。1948年的一次跨国赛跑比赛中,他跑赢了同年奥运会银牌得主。.

一阶逻辑和艾伦·图灵 · 停机问题和艾伦·图灵 · 查看更多 »

集合

集合可以指:.

一阶逻辑和集合 · 停机问题和集合 · 查看更多 »

数理逻辑

数理逻辑是数学的一个分支,其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。数理逻辑是数学基础的一个不可缺少的组成部分。 数理逻辑的研究范围是逻辑中可被数学模式化的部分。以前称为符号逻辑(相对于哲学逻辑),又称元数学,后者的使用现已局限于证明论的某些方面。.

一阶逻辑和数理逻辑 · 停机问题和数理逻辑 · 查看更多 »

上面的列表回答下列问题

一阶逻辑和停机问题之间的比较

一阶逻辑有83个关系,而停机问题有15个。由于它们的共同之处5,杰卡德指数为5.10% = 5 / (83 + 15)。

参考

本文介绍一阶逻辑和停机问题之间的关系。要访问该信息提取每篇文章,请访问:

嘿!我们在Facebook上吧! »