证明在 {a} 上不可递归枚举的所有语言的集合是不可数的吗？
递归可枚举语言是接受每个字符串的语言，否则不接受。如果一种语言在每个字符串上都停止，那么我们将其称为递归语言。
问题
我们需要证明所有在{a}上不可递归枚举的语言的集合是不可数的。
首先让我们看看递归可枚举语言是什么-
递归可枚举语言
如果L是某个TM接受的字符串集，则语言L是递归可枚举的。
如果L是递归可枚举语言，则-
如果w∈L那么TM在最终状态停止，
如果w∉L则TM在非最终状态中停止或永远循环。
如果L是递归语言，则-
如果w∈L那么TM在最终状态停止，
如果w∉L则TM停止在非最终状态。
现在，通过理解递归可枚举语言的定义，证明所有在{a}上不可递归枚举的语言的集合是不可数的。
证明
步骤1-让我们假设S是字母表∑上所有语言的集合。
Step2-让我们假设所有语言的集合S都是不可数的。
步骤3-集合S是两个集合S1和S2的并集，因此，集合S1由所有递归可枚举语言（图灵机接受的语言）组成，并且，集合S2由所有非递归可枚举语言组成语言（注意S1'=S2）。
第4步-现在，我们必须证明S2是不可数的。因为我们有S=S1∪S2。我们知道集合S1是可数的，因为图灵机的集合是可数的。
Step5-如果S2是可数的，那么我们可以说集合S也是可数的（因为两个可数集合的并集是可数的）。但这不可能，因为集合S是不可数的。因此，我们可以说集合S2是不可数的。