从递归函数到递归语言

这篇文章简要叙述如何从逻辑理论中的递归函数定义形式语言理论中的递归语言。相关的概念都是按照通用的理解，其中形式语言的部分参照Hopcroft的那本自动机教材。

Church-Turing论题保证了图灵机所能计算的函数为全部的递归函数。当提到「递归函数」时，我指的不仅是全函数，当然也包括偏函数的情况。

CT论题对很多不同变体的图灵机定义都成立，但这些图灵机大体都是按照经典的七元组形式定义的。有的形式没有终止状态集，靠的是停机后的纸带状态来定义函数的值；不过这和额外限定了停机时必须处于终止状态的图灵机是等价的（强可计算性与可计算性等价）。

无论如何，图灵机必须允许有可能在某些输入上不停机，这一点是定义全部（偏）递归函数的必要条件。这和形式语言理论中递归语言的定义看上去不一致：L是递归的，当且仅当存在一个图灵机M接受的语言等于L，且无论输入如何M总会停机。

这种不一致只是一种错觉罢了。当我们用图灵机定义语言L的时候，实质是定义了一个字符串集合，或者说性质（即一元谓词）P。性质P的递归性，等价于其特征函数$C_rp(w)$的递归性。对于一个关系而言，其特征函数总是全函数。因此在任何输入串下M都会有输出，也就必然停机。

如果已知M是可计算递归函数$C_rp(w)$的图灵机，那么按照定义，M最后会把纸带改写为1或者0。很容易构造出另一个图灵机N模拟M，使得N在形式语言理论意义下接受语言L。事实上，只需要在M的转移图上加上一个终止状态和若干转移，以读取M停机后的纸带状态就可以了。

因此，递归语言也可以这么定义：语言L称为是递归语言，当且仅当其特征函数C是递归函数。严谨一点的话，应该加上对字符串输入进行哥德尔编码的过程，不过这不影响直观的理解。