证明半可判定语言

Question

我要证明"Semidecidable languages are closed by the direct morphism operation"

我认为一个从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* 计算 E* 中的 v = p(w)。
2. 模拟 TML(v)。如果 w\in s(L) 那么 v\in L 并且机器接受。