递归语言

在数学、逻辑学和计算机科学中，如果一种形式语言（取自固定字母表的符号有限序列的集合）是该语言字母表上所有可能的有限序列集合的递归子集，则称为递归。等价地，如果存在一个全图灵机（对每一个给定的输入都会停止的图灵机），当给定一个有限的符号序列作为输入时，如果它属于该语言，就接受它，否则就拒绝它，那么这种形式语言就是递归的。递归语言也被称为可解码语言。可判定性的概念可以扩展到其他计算模型。例如，我们可以谈论在非决定性图灵机上可解码的语言。因此，只要有可能出现歧义，递归语言的同义词就是图灵可判定语言，而不是简单的可判定。所有递归语言的类别通常被称为R，尽管这个名字也被用于RP类。这种类型的语言在(Chomsky1959)的Chomsky等级体系中没有定义。所有的递归语言也是可递归列举的。所有正规的、无语境的和语境敏感的语言都是递归的。

对于递归语言的概念，有两个相当的主要定义。递归形式语言是该语言字母表上所有可能的词语集合中的一个递归子集。递归语言是一种形式语言，对于这种语言，存在一台图灵机，当遇到任何有限的输入字符串时，如果该字符串在该语言中，则停止并接受，否则停止并拒绝。图灵机总是停止：它被称为决定者，并被称为决定递归语言。根据第二个定义，任何决定问题都可以通过展示其在所有输入上终止的算法而被证明是可决定的。不可决断的问题是一个不可决断的问题。

如上所述，每个上下文敏感的语言都是递归的。因此，递归语言的一个简单例子是集合L={abc,aabbcc,aaabbbccc,...}；更正式地说，集合{displaystyleL={{a,b,c}{*}midw=a{n}b{n}c{n}{mbox{forsome}ngeq1,}}。是对环境敏感的，因此是递归的。不具有上下文敏感性的可解码语言的例子更难描述。对于这样一个例子，需要对数理逻辑有一定的熟悉。Presburger算术是自然数的一阶理论，有加法（但没有乘法）。虽然普斯伯格算术中形式良好的公式集是无语境的，但每个接受普斯伯格算术中真实语句集的确定性图灵机的最坏情况下运行时间至少为{displaystyle2{2{cn}}}，对于某个常数c>0，最坏情况下的运行时间为，对于一些常数c>0（Fischer&Rabin1974）。

这里，n表示给定公式的长度。由于每一种上下文敏感语言都可以被线性有界自动机所接受，而且这样的自动机可以被确定性的图灵机所模拟，其最坏情况下的运行时间最多为{displaystylec{n}}对于某个常数c对于某个常数c，普氏算术中的有效公式集不是对环境敏感的。从正面看，已知有一台确定性的图灵机，其运行时间最多为n的三倍指数，可以决定普雷斯堡尔算术中的真实公式集（Oppen1978）。因此，这是一个可解的语言的例子，但不是上下文敏感的。

递归语言在以下操作下是封闭的。也就是说，如果L和P是两个递归语言，那么下面的语言也是递归的。克莱因星L最后一个属性来自于集差可以用交集和补集来表示的事实。