从丘奇-图灵论题到多奇原理

本文对丘奇-图灵论题提出的背景，以及为什么哥德尔没有提出丘奇论题，而且直到给出图灵机概念之后才逐渐接受丘奇。图灵论题的真正原因作出某种解释，基于这种解释，将对多奇给出的“丘奇-图灵论题的物理版本”的内涵及意义作出评价，对量子计算机的计算本质给出逻辑分析。

语境与丘奇-图灵论题意义的演变

丘奇-图灵论题是一个关于计算的基本假设。文章主要探讨了三种不同语境下丘奇-图灵论题的形式和意义,指出人们对计算的认识是随语境转换而变化的,将计算视为信息处理的过程,利用自然系统的演化来实现计算,是未来计算科学的主要发展方向。

时间旅行的量子门

量子计算可以解决经典计算难于求解的问题,在物理原理允许范围内扩大了可有效计算的问题范围,对经典计算的扩展丘奇图灵论题提出了挑战.这里我们讨论一个有趣的问题:通过突破物理原理限制来实现更强大的计算机,进一步扩展量子计算机的能力.我们考虑一种全新的操纵能力,让量子计算可以实现时间穿梭旅行的量子控制门.这是量子门线路图形语言的一个符合直觉的扩展,作为例子,我们展示了一个可以有效求解SAT难题的扩展量子算法.我们的结果有助于更深刻地理解计算和物理原理之间的关系.

丘奇-图灵机器人如何跨越恐怖谷

尽管人工智能技术在数据挖掘、图像识别和统计预测等领域成就非凡,但机器人与环境的交互能力还亟待提升。作为涉身认知的起源之一,affordance概念常常被用来描述或解释人类、动物与环境进行互动的方式。目前,这个来自于生态心理学的理论也激发了人们对机器人设计的全新思路。机器人也可以被当作自主的行动主体,能够根据自身的物理能力来与环境进行有效的交互活动。通过理论论证和新近研究,吉布森的social affordance理论也能够在复杂的社会交往环境下,对机器人与人类的社交进行计算机意义上的语言描述。因此,该理论可以为未来机器人的设计与研发提供一个可靠的方向。

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

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

关于计算的若干哲学思考

计算无疑已经成为我们这个时代最有影响的概念之一,然而,人们对于究竟什么是计算却存在着各不相同的看法。本文基于对计算概念的拓展过程和不同诠释的考察,提出并论证了一种关于计算的广义规定,即计算就是信息加工的过程;在此基础上,进一步探讨了与计算概念密切相关的丘奇-图灵论题和正在兴起的泛计算主义思潮。

宇宙是一个计算机吗?——论基于自然计算的泛计算主义

泛计算主义是基于前沿科学的发展提出的一种新的世界观,这种世界观认为,宇宙是一个巨大的计算系统。早期的泛计算主义主要基于图灵计算范式。这种版本的泛计算主义自提出以来,受到了许多批评,尤以信息哲学家弗洛里迪和心灵哲学家皮西尼尼为代表。在回应批评的过程中,瑞典信息哲学家多迪格-瑟恩科维奇基于自然计算范式发展提出了一种新的泛计算主义——信息—计算主义,为泛计算主义提供了新的不可或缺的辩护。新的泛计算主义把宇宙展现为一个在不同组织水平上通过信息交互而形成的能动者网络。

计算的极限

计算深刻地影响着人们的日常生活和生产活动,也推动了诸多其他科学领域的发展和变革.本文从几个不同的方面探讨计算的能力和极限.从计算的模型和丘奇图灵论题,到P和NP问题的深远影响及量子计算对传统计算的冲击,我们深入讨论了对计算极限的理解.