以词典形式列举图灵可识别的语言



,因此也可以枚举图灵的可识别语言。

但是,枚举者是否可以按词典顺序"打印"图灵可识别的语言?

no。假设这是可能的。然后可以确定语言如下:

  1. 开始按顺序列举所有接受的字符串。
  2. 如果您列出了一个词典订单大于您要寻找的字符串的字符串,请停止拒绝。
  3. 如果您列出了要寻找的字符串,请停止接受。

这最终将对任何输入字符串终止,因为对于任何给定的输入字符串,只有有限的许多枚举字符串就存在较小的词典顺序。如果它找不到您的目标字符串,它将始终停止拒绝,如果这样做,它将始终停止接受。不必担心丢失字符串,因为它知道您的字符串应该在哪里,这要归功于列出的字符串。

,由于我们知道有枚举的语言不是无法决定的,因此我们不能按顺序枚举枚举的语言。

最新更新