我必须证明语言 L = {< M >: |L(M)| <= 2016} 不是半可判定的。现在我想这样做：
取一个随机字母 E。现在 E 中有无限个单词。我们只能得出 |L(M)| <= 2016 通过将 E* 中的每个单词作为输入传递给 M。但是由于单词的数量是无限的，这意味着我们必须将输入传递给 M 无数次。但这意味着执行这些检查的图灵机最终会陷入无限循环，因此永远不会返回接受或拒绝它的输入。因此语言 L 不是半可判定的。
但我认为这可能不够正式？主要是因为我只是假设检查这种语言的图灵机会让 M 在 E* 中的每个单词上运行。这个假设是否有效，还是我应该更正式？
考虑 L 的补码：图灵机编码的语言，其语言包含超过 2016 个字符串。我们可以很容易地证明这种语言是半可判定的。鉴于这一事实，假设 L 也是半可判定的。因为 L 及其补码都是半可判定的，所以我们有一个有效的程序来决定每一个：交替运行 L 及其补码的 TM，最终将列出输入。
为了看到 L 的补码是半可判定的，想象一个 TM 对每个可能的输入执行 M 的一步，交替移动，以便每个字符串最终由 TM 的任意多次移动处理。它访问输入的顺序如下：
e,
e, 0,
e, 0, 1,
e, 0, 1, 00,
e, 0, 1, 00, 01, ...
显然，任何输入字符串最终都会被处理多次。我们的机器模拟 M 在所有可能的输入字符串上运行，一次一步，最终会发现 2017 字符串导致 M 停止接受，否则它将永远运行。如果它发现 2017 字符串有效，它会停止接受。