1

我知道如果存在用于一种语言的图灵机，那么该语言是递归可枚举的，因此存在它的枚举过程。但是，如果一种语言是可数的，这是否意味着它必须有一个 TM 呢？

谢谢！

4

1 回答 1

1

集合 Σ* 是一个可数集合，所以它的所有子集都是可数的。这尤其意味着，每一种无限语言都是可数的，即使并非所有无限语言都是递归可数的。因此，有无数种不存在 TM 的无限语言。

希望这可以帮助！

于 2014-12-30T01:38:20.977 回答