computation-theory - 可判定语言（计算模型）

Question

我需要证明 L 是否可判定：

L={<M> | M 是一个 TM，L(M) 和 H_TM 的并集在 RE}

（ H_TM={<M,w> | M 是一个在 w} 上停止的 TM）

Answer 1

我想 <...> 是哥德尔化中 TM 的编号。L(M) 是一组单词，而 H_TM 是一组对。因此它们的联合是不相交的，两者都不会出现任何元素。因此，联合是可枚举的，当且仅当它的两个部分是。H_TM 是可枚举的，因此可枚举性仅取决于 L(M)。但是，作为 TM 的语言意味着可以确定，因此可以清楚地枚举。因此，L 的定义中关于 M 的条件始终为真，因此 L 是所有 TM 描述的集合，它是有规律的且可明确判定的。