这种语言是否可确定

Question

L = {（ ， ，x）| M1（x）严格执行多于M2（x）的步数}。 （如果两个计算都是永久运行的，那么两个计算都不会比另一个严格得多）。

该语言是否可判定？如何证明它？

Answer 1

作为评论中的templatetypedef提示，此语言是不可判定的。如果它是可确定的，你可以按如下方式决定暂停问题。

首先，让M1为任何无法停止输入x的TM。这样一个TM可能是一个微不足道的，它有两个左右移动的状态，不会改变磁带。让M2成为任何TM。现在，您的语言决策者可以回答“M2是否停止所有输入”的问题，这相当于暂停问题。您也可以让M2成为TM，它首先确认磁带上的任何特定输入w，然后根据某些TM M3继续。这会将问题改变为“M3是否停止输入w”，这可能是问题的更规范的版本。