大门|大门-CS-2001 |问题32

考虑下面的问题X。

Given a Turing machine M over the input alphabet Σ, any
state q of M And a word w∈Σ*, does the computation of M
on w visit the state q? 

以下关于X的陈述哪项是正确的？ （A） X是可判定的 （B） X是不可判定的，但部分可判定 （C） X是不可判定的，甚至不是部分可判定的 （D） X不是一个决策问题 答复: （B） 说明： 这个问题是一个状态进入问题。状态进入问题可以归结为停止问题。 我们构造了一个最终状态为q的图灵机M。我们运行一台图灵机R（用于状态输入问题） 输入：M，q，w。 我们把w作为M的输入。 如果M在最终状态“q”中停止，则R接受输入。所以，给定的问题是部分可判定的。

如果M进入无限循环，那么M不能输出任何东西。因此，R拒绝输入。因此，给定的问题变得不可判定。 因此，选项（B）就是答案。 如果你在上面的帖子中发现任何错误，请在下面发表评论。 这个问题的小测验