如何知道图灵机是否是决策者？

Question

有没有简单的方法来解决这个问题？看图灵机图能不能判断是不是decider？

Answer 1

决策器是一台在所有输入上都停止的机器。 There is no general way to prove whether a given machine halts on all inputs.

如果你有一台特定的机器，你可以尝试正式证明所有执行路径都停止了。例如，如果您的机器的读取头在每次转换时始终向右移动（从不向左移动），并在没有更多输入时停止，那么对于所有有限输入，机器将停止。一个更简单的例子是一台只有一个状态的机器：halt.

Answer 2

TM 决定语言 L 当且仅当 1- 字符串 L 将 M 置于 Accept 状态 2- NOT IN L 中的字符串将 M 置于 Reject 状态

TM M 识别语言 L 当且仅当 1- 字符串 L 将 M 置于 Accept 状态 2- 字符串 NOT IN L - 要么将 M 置于 Reject 状态 - 或者使 M 循环

@乔万慧你是说 "TM changes between two states and both states are neither accepting nor rejecting states, is this Turing decidable?" 那么它肯定会无限前进，即它会进入图灵可识别的循环。

Answer 3

你可以一般地证明

DECIDER_tm = { <M> : TM M is a decider } is undecidable.

反证法。假设它是可判定的，让 R 成为 DECIDER_tm 的决策者。

使用 R 作为子程序为 HALT_tm 构造 S 决策器。

S = on input <M,w>
1. construct M_w = " on input x" 
    run M on w
    if M accepts accept. if M rejects reject.
2. Run R on M_w
3. If R accept => accept, if R rejects => reject.

请注意，如果 M 接受或拒绝 w，M_w 暂停所有输入，R 接受，因为 M_w 是决策者。如果 M 在 w 上循环，M_w 在所有输入上循环，R 拒绝 M_w。

我们已经为 HALT_tm 构建了一个决策器，因为我们知道 HALT_tm 是不可判定的，我们的假设是错误的 => DECIDER_tm 是不可判定的。

如何知道图灵机是否是决策者？

How to know if a Turing Machine is a decider?

turing-machines