约翰·马丁语言概论与计算理论书

Question

证明了如果L⊆Σ*和L是无限且递归可枚举的，则L有一个非递归可枚举的无限子集和一个递归可枚举但不是递归的无限子集。

Answer 1

我们不需要依赖于L是递归可枚举的事实来显示这些东西；所有无限的字符串集都有不可递归枚举和递归可枚举但不是递归的子集。考虑这个问题有很多不同的方法，但下面的方法非常简单。

无限集Σ*的基数与自然数的基数相同。这是“最小”无穷大，因为自然数集合可以映射到任何其他无限集合(尽管相反不一定是正确的；例如，reals不能映射到自然中而不存在实质性的重叠)。因此，Σ*的任何无限子集也必须具有相同的基数；也就是说，任何无限的字符串集都可以与自然数直接一对一地对应。我们可以为Σ*构造这样的映射，如下所示:以增加字典顺序的Σ*字符串为基础，将第一个字符串映射为0，第二个字符串映射为1，等等。通过给Σ中的每个符号赋值，从0到\x，Σ=- 1，我们甚至可以设计一个程序来计算字符串的对应自然数。例如，假设Σ= {a，b，c}，那么Σ*的字符串是：

string    position
e         0
a         1
b         2
c         3
aa        4
ab        5
ac        6
ba        7
bb        8
bc        9
ca        10
cb        11
cc        12

这意味着将1、2和3的值分别赋值给a、b和c，然后为word w计算i=1的3^(x=1)的和。因此，字符串504对应于自然数1_3^5 + 2_3^4 + 3_3^3 + 1_3^2 + 2_3^1 + 3_3^0 = 243 + 162 + 81 +9+6+3=504。

类似地，由于Σ*的任何无限子集的基数都必须是x-Σ* --所以在子集的字符串和自然数之间存在一些映射；等价地，在子集的字符串和Σ*的字符串之间存在映射。找出一个特定的子集可能很困难，甚至是不可能的。如果你搞清楚了，实际上计算映射可能很困难或者不可能。但是，在理想形式的柏拉图宇宙中，这种映射是存在的，这对我们目前的目标来说就足够了。让我们来看看使用符号f-一些将Σ*映射到问题语句中假设的递归可枚举子集的映射。

以Σ*的任何非递归可枚举子集为例。那么调用这个R，让R‘成为Rw.r.t的图像。映射f；即R‘是从R的字符串映射到的子集中的字符串集合，但是R’也不能递归枚举，因为如果是的话，我们可以使用f，f‘的逆来递归枚举R，如下所示:枚举R’中的字符串，对于每个这样的字符串w，输出字符串f'(w)。这将枚举R中的所有字符串，我们说这是不能完成的。因此，我们知道R‘不能是递归计数的。

以Σ*的任何递归可枚举但非递归子集为例。那么，让S‘成为Sw.r.t的形象。映射f；即S‘是子集中的一组字符串，从S的字符串映射到S，然后是S：

1. 必须是递归枚举的。这是正确的，因为我们可以枚举S中的字符串，对于每个这样的字符串，输出f( w )，从而枚举S‘中的字符串。所以，S‘是recursively-enumerable.

1. 不能是递归的，因为如果是的话，我们可以为S‘中的成员问题生成一个决策器，并使用它来确定S中的成员资格如下:对于查询字符串w，我们要确定它在S中的成员资格，检查f(w)是否属于S'；如果是，那么w在S中，否则就不是。但是我们说S不是递归的，所以S‘也不能是递归的。