什么是图灵机正在停摆？

Question

我是新的可判定性。我读过停止问题，但没有得到任何实际上暗示的东西。我已经搞砸了解释。

任何人都可以提供我任何声音的解释或至少一些细节，这将有很大的帮助？

Answer 1

您可以将图灵机想象成一种可以执行程序的理论计算机。图灵机的程序由一组状态和这些状态之间的转换组成。运行在图灵机上的程序可以访问一个叫做磁带的输入源，它有一些可以处理程序的字符串（可能是空的）。图灵机的所有程序要么是return true（halt-accept），要么是return false（停止拒绝），要么根本没有return任何东西 - while (true) ; return true;。根据您的定义，机器可能也会有throw的异常（崩溃）;但通常崩溃被认为是像try { /*crash*/ } catch (Exception) { return false; }这样的崩溃意味着停止拒绝。

停机问题，那么，是是否可以编写一个程序对于一个图灵机，其输入为图灵机另一程序和输入的一些字符串，它返回true或false（停止-接受或停止，拒绝）如果程序已经停止了提供的输入并返回false否则（即，如果程序永不停止）。

事实证明，答案是没有这样的通用程序存在于图灵机上。假设一个确实存在，M。给定输入m和i它接受如果m在i停止并且否则拒绝。我们可以专门用来愚弄M另一个程序：

N(i) 
1. if M(N, i) then loop forever; 
2. otherwise return true 

现在是否继续工作M上N：

1. 假设M说，在输入iN暂停。然后N将永久循环，并且M将会出错。

2. 假设M说N永远循环输入i。那么N将返回true和halt，因此M将会出错。

在这两种情况下，M想出了错误的答案对于我们N，因为我们在关于M比它的存在并解决停机问题，其他任何假设，我们不难得出结论，没有任何机器可以解决存在暂停问题。

（M如果不希望直接引用M，则可以将其作为输入传递给程序N作为输入）。