computation-theory - 证明半可判定语言

Question

我必须证明“半可判定语言被直接态射运算封闭”

我认为从 E 到 F 的直接态射是一对态射 s: E -> F, p: F->E, 其中 p · s = IdE。

所以我的建议是用图灵机做一个证明，因为图灵可识别的语言在∪、°、*和∩下是封闭的，但我不知道如何用在 TM 中运行的特定语言来证明它（如果我的建议是正确的） .

Answer 1

由于您的语言 L 是半可判定的，因此存在一个图灵机 TML，它在 E 中的每个输入上都停止。您需要一个用于语言 K = s(L) 的机器 TMK。

1. 在输入 w\in F* 上计算 v = p(w)，它在 E* 中。
2. 模拟 TML(v)。如果 w\in s(L) 那么 v\in L 并且机器接受。