证明语言是图灵可识别的iff可计算地枚举

Question

这个证据的一个非常小的问题，我在啜饮者中找到了圣经3.21，在我的讲义中。

在“才能”方向上，我们假设一个图灵机 $ m $ 识别某些语言 $ l $ 。我们列出了输入字母中的所有字符串（以词典顺序，例如 $ s_1，s_2，s_3，\ dots $

然后，我们构建一个枚举者 $ e $ ，每个 $ i= 1,2,3，\ dots $ 简单运行 $ m $ for $ i $ 步骤每个输入 $ s_1，s_2，s_3，\ dots，s_i $ ;然后它打印任何 $ s_j $ ，由 $ m $ 接受。 $ e $ 是我们需要的。

现在，由于我知道字符串是有限的，为什么我应该运行 $ m $ for $ i $ 步骤在第一个 $ i $ 字符串时，我可以在上$ i $ -th字符串？感觉像不必要的并发症。

p.s。询问了另一个问题，但它解决了不同的疑问： 问题“只有在定理的”部分“时，语言是图灵识别的IFF，某些枚举器枚举它。”

Answer 1

如果您运行 $ m $ $ i $ -th字符串，那么它可能永远不会停止，所以您的算法将被卡住。这个想法是，如果 $ m $ 在 $ i $ -th字符串上会停止，则 $ j $ 步骤，然后我们将在进入 $ \ max（i，j）$ -th字符串。