不接受的图灵机--我们怎么知道呢？

Question

假设我有一个接受语言L的TM M，如果我给它输入单词w，并且想知道它是接受还是循环--如果M不接受w，我可以不解释我做了什么吗？

我的意思是-短语“如果M不接受w”假设每个算法都可以隐式地识别一个无限循环。

我在还原性问题中看到了很多，其中M是一个使用M的可接受性以及M的non-acceptance的算法的内部TM，而我从未见过外部算法如何能够知道M不接受的解释。刚才说：“如果我接受.否则.”，算法怎么能检测到“否则”部分呢？在无限循环的情况下，如何检测到它？

谢谢

Answer 1

一般来说，你不能通过算法检测到TM不会停止在给定的输入上。

为了“如果我接受.否则.”问题，一种可能是，其他部分总是导致不接受.在这种情况下，内部TM循环与否并不重要。如果是这样的话，外部的也会循环而不接受。因此，其他部分不需要执行。

另一个可能的情况是，您只查看内部TM中的递归/可判定语言。那你永远都会得到答案的。