图灵机箭头定义

Question

有人知道“=>”、“<=”和“<=>”在图灵机上下文中的确切定义吗？谷歌搜索未能为我提供答案！

为了把它放在上下文中，这里有一个定理/证明。

_

定理 语言 L 是可判定的 <=> L 和 L' 都是图灵可识别的。

证明: => 很明显。对于 <=，我们有 TM 的 M1 和 M2 分别识别 L，L'。使用它们构建一个并行运行 M1 和 M2 的 TM M，直到其中一个接受（这是必须发生的）。如果 M1 接受 M 也接受；如果 M2 接受，则 M 拒绝。

Answer 1

定理 语言 L 是可判定的当且仅当 L 和 L' 都是图灵可识别的。

证明：L是可判定的意味着L和L'是图灵可识别的是显而易见的。对于 L 和 L' 都是图灵可识别的意味着 L 是可判定的，我们有 TM 的 M1 和 M2 分别识别 L，L'。使用它们构建一个并行运行 M1 和 M2 的 TM M，直到其中一个接受（这是必须发生的）。如果 M1 接受 M 也接受；如果 M2 接受，则 M 拒绝。

<==>表示当且仅当。 A => B 表示 A 蕴含 B。在当且仅当证明中，我们证明双重蕴涵。换句话说，为了证明 A 当且仅当 B 那么我们证明 a 蕴含 B 并且 B 蕴涵 A。