在可计算性理论中,超递归算法是具有比图灵机更强大计算能力的普通算法的推广。这个术语由马克·布尔金(Mark Burgin)提出,他的著作《超递归算法》发展了该理论并提出了几个数学模型。图灵机和其他传统算法的数学模型允许研究人员找到递归算法及其计算的属性。类似地,超递归算法的数学模型,例如归纳图灵机,允许研究人员找到超递归算法及其计算的性质。
Burgin,以及包括Selim Akl、Eugene Eberbach、Peter Kugel、Jan van Leeuwen、hava siegelmann、Peter Wegner和jiříwiederman在内的其他研究超递归算法并为之做出贡献的研究人员,都认为超递归算法可以用于证伪丘奇-图灵论题,但这一观点在数学界受到了批评,并没有被广泛接受。
布尔金(2005: 13)使用“递归算法”这个术语来表示可以在图灵机上实现的算法,并且在更一般意义上使用了“算法”这个词。那么“超递归类算法”就是“一类无法在图灵机上实现的函数计算算法”(布尔金2005: 107)。
超递归算法与超计算密切相关,其关系类似于普通计算和普通算法。计算是一个过程,而算法是对该过程的有限构造描述。因此,超递归算法定义了“递归算法无法实现的计算过程(包括输入和输出过程)”(布尔金2005: 108)。更严格的定义要求超计算解决超问题。
超递归算法也与算法方案相关,算法方案比超递归算法更通用。布尔金认为(2005: 115)有必要明确区分超递归算法和那些非算法的算法方案。在这种区别下,某些种类的超计算是通过超递归算法获得的,例如归纳图灵机,而其他类型的超计算是由算法模式引导的,例如无限时间图灵机。这解释了超递归算法与超计算的关系,反之亦然。基于该论点,超递归算法只是定义超计算过程的一种方式。
超递归算法的例子包括(布尔金2005: 132):
算法方案的例子包括:
归纳图灵机实现了一类重要的超递归算法。归纳图灵机是能完成特定任务的确定指令列表,当给定一个初始状态时,它将经过一系列明确定义的连续状态,最终给出最终结果。归纳图灵机和普通图灵机的区别在于,普通图灵机在获得结果时必须停止,而在某些情况下,归纳图灵机可以在获得结果后继续计算,而不会停止。克莱尼用“计算程序”或“算法”以描述永远运行的程序(克莱尼1952:137)。克莱尼还要求这样的算法最终必须展示“某个对象”(克莱尼1952:137)。布尔金认为归纳图灵机满足这一条件,因为它们的结果在有限的步骤后显示出来。归纳图灵机在最终输出产生时不能被指令停止的原因是,在某些情况下,归纳图灵机可能不知道在哪个步骤获得了结果。
简单归纳图灵机等价于其他计算模型,例如施密休伯的一般图灵机、希拉里·普特南的试错判断、戈尔德的限制部分递归函数、欣蒂卡和穆坦的试错机(1998)。更先进的归纳图灵机更强大。归纳图灵机的层次结构可以决定算术层次结构中任意集合的成员 (布尔金2005)。与其他等效计算模型相比,简单归纳图灵机和一般图灵机给出了完全基于物理机的计算自动机的直接构造。相比之下,试错判断、限制递归函数和限制部分递归函数仅表示符号的语法系统及其操作的形式规则。简单归纳图灵机和一般图灵机与限制部分递归函数和试错判断有关,正如图灵机与部分递归函数和演算有关。
归纳图灵机的非停止计算不应与无限时间计算混淆。首先,一些归纳图灵机的计算确实停止了。与传统图灵机的情况一样,一些停止的计算给出了结果,而另一些则没有。即使它不停止,归纳图灵机也会不时地产生输出。如果该输出停止变化,则被视为计算结果。
普通图灵机和简单归纳图灵机有两个主要区别。第一个区别是,即使是简单的归纳图灵机,相比传统图灵机具有更高的性能。第二个区别是,传统的图灵机将总是能确定(通过进入最终状态)何时获得结果,而简单的归纳图灵机在某些情况下(例如当“计算”普通图灵机不能计算的任务时),将不能确定输出结果的时间。
如果一个通用图灵机上有一个有限的、可能不停机的程序递增地输出一个符号序列的每一个符号,那么这个符号序列是可计算的。这包括π的并矢展开,但仍然排除了大多数实数,因为大多数实数不能用有限程序来描述。传统带有只读输出带的图灵机,不能编辑它们以前的输出;根据Jürgen Schmidhuber,广义图灵机可以编辑它们的输出带和工作带。他将可构造描述的符号序列定义为在广义图灵机上运行有限的、非停止的程序的符号序列,使得任何输出符号最终收敛,即在某个有限的初始时间间隔之后不再改变。Schmidhuber (2000,2002)使用这种方法来定义一组形式上可描述或可构造计算的通用规则或万物构造理论。广义图灵机和简单归纳图灵机是最接近递归算法的两类超递归算法(Schmidhuber 2000)。
递归理论中的丘奇-图灵论题依赖于术语“算法”的特定定义。基于比递归理论中常用的定义更一般的定义,布尔金认为超递归算法,例如归纳图灵机,否定了丘奇-图灵理论。他进一步证明了超递归算法理论上可以提供比使用量子算法更大的效率增益。
布尔金对超递归算法的解释在数学界遭到了反对。其中一位反对者是逻辑学家马丁·戴维斯,他认为布尔金的主张已经被很好地理解了“几十年”。戴维斯说,
“目前的批评不是关于这些问题的数学讨论,而是关于当前和未来物理系统的误导性主张。”(戴维斯2006: 128)
戴维斯反驳了布尔金的说法,即设定在算术等级的第二级可以称为可计算的,他说
“一般认为,要使计算结果有用,必须至少能够认识到它确实是所寻求的结果。”(戴维斯2006: 128)
暂无