证明半可译语言

Question

我必须证明“半可译语言是由直接的态射运算关闭的”。

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

所以我的porposal是用图灵机器来证明的，因为图灵可识别的语言在∪，°，*和∩下是封闭的，但是我不知道如何用TM中运行的特定语言来证明它(如果我的提议是正确的)。

Answer 1

由于您的语言L是半可选的，因此存在一个图灵机TML，它在E中的每个输入上都会停止。您希望为语言K= s(L)提供一个机器TMK。

1. 在输入w*时，计算v= p(w)，它在E*中。
2. 模拟TML(v)。如果w\in s(L)，则v\in L和机器接受。