theory - 主要素数 TM 是可判定的吗？

Question

字母 Σ 上的语言 L 主要是素数当且仅当对于每个长度 l，如果 l 是素数，大多数长度为 l 的字符串确实属于 L，但如果 l 是合数，则不属于 L。令 PriPriTM = {〈M〉 : L(M) 主要是素数并且 M 是一个 TM}。

PriPriTM Turing 是可判定的吗？

Answer 1

这是一个非常复杂的决策问题，但答案是不，不可能确定 TM 是否接受主要的主要语言。为什么？一些 TM 主要接受素数语言（考虑一个完全接受素数长度字符串的 TM），而有些则不接受（考虑接受前者语言的补码的 TM）。该属性是语义的，因为它处理语言中的字符串 - 而不是句法，处理 TM 本身的形式。换句话说，接受相同语言的两个 TM 总是会被我们问题的决策者同等对待。那么，根据赖斯定理，决定 TM 是否决定这种语言的问题是不可计算的。