字母Σ上的语言L主要是素数，当且仅当对于每个长度l，如果l是素数，则长度为l的大多数字符串属于L，但如果l是复合数，则不属于L.设PriPriTM = {<M>：L（M）主要是素数，M是TM}。
PriPriTM图灵是否可判定？
这是一个非常复杂的决策问题，但答案是否定的，TM是否接受主要的主要语言是不可能判定的。为什么？有些TM主要接受主要语言（考虑TM接受完全长度的字符串），有些则不接受（认为TM接受前者语言的补充）。该属性是语义的，因为它处理语言中的字符串 - 而不是语法，处理TM本身的形式。换句话说，对于我们的问题，接受相同语言的两个TM将始终由决策者相同地对待。那么，根据莱斯定理，决定TM是否决定这种语言的问题是不可计算的。