能行可计算性函数渐进优超等价类的可达性质

利用理想计算机 URM关于能行可计算性函数的定义以及渐进分析的方法对能行可计算性函数进行分类后 ,建立了能行可计算性函数渐进优超等价类子结构 ,并通过引进可达性概念研究能行可计算性函数渐进优超等价类之间的关系 ,证明了任何一致无界能行可计算性函数渐进优超等价类都具有强不可达性质 .此成果对算法复杂性函数渐进优超等价类数学结构的进一步研究有一定参考价值 .

递归函数的哲学意义及其演进历史

递归函数的根本特征在于其逐步计算和分解计算,即通过某函数带入到(返回,即"递归")自身或另一个函数的变量来求解被带入函数。这个定义是历史上逐步定型化的,其定型的过程始终保持了其这一原始意义,但其函数的形式是逐步严格化的,其类型是逐步扩大的。当前,普遍地接受的"递归函数"即指哥德尔于1934年定义的"广义递归函数(一般递归函数)",包括μ-递归函数、阿克曼递归函数以及在逻辑上可能出现的其他递归函数;广义递归函数在外延上与下列概念具有逻辑等值意义:递归函数、能行可计算函数、λ-可定义函数、图灵可计算函数——这些函数都是广义递归函数的不同侧面的反映。

论人工智能科学诞生的逻辑背景

论人工智能科学诞生的逻辑背景王建芳人工智能科学的诞生同其他许多自然科学相似，既需要一定的思想基础，又必须借助一定的物质手段。在对人工智能科学诞生行程的历史回顾中，我们会清楚地看到，人们对于它的构想与实践，与逻辑科学的演化与发展密切相关。一些逻辑学家为...

哥德尔与可计算性理论——哥德尔可以有丘奇-图灵论题吗?

将非形式的“能行可计算性”概念等同于严格的数学概念“一般递归函数”或是“图灵可计算性”,这被称之为“丘奇-图灵论题”(Church-Turing Thesis,CTT),它被视为用逻辑的方式来澄清概念的一个典范。本文以哥德尔在可计算性理论发展中的角色为参照点,从历史考察以及哲学分析的角度来试图回答这样两个相关的问题:虽然哥德尔已经掌握了足够的技术细节,但是他为什么不愿意提出一个后来被证明是和CTT等价的“哥德尔论题”?其次,尽管对丘奇论题非常不满,但是为什么哥德尔后来还是为图灵的分析信服而最终愿意相信CTT的正确性?本文将从哥德尔的概念实在论视角出发提出一个不同于费佛曼和戴维斯的回答,并且以概念分析的公理化方法考察图灵论题相对于丘奇论题的优越性,以期更好地理解哥德尔的实在论和CTT所带来的认识论挑战。