两种图灵可判定语言的交集是图灵可判定的

Question

证明两种图灵可判定语言的交集是图灵可判定的。(给定决定每种语言的算法，描述确定字符串是否属于交集的算法。)

我知道，如果有一种算法来决定成员资格，一种语言是图灵可决定的。然而，我不确定从哪里开始这个证明。

任何帮助都将不胜感激！

Answer 1

首先，您需要定义交叉点是什么。它是属于这两种语言的所有字符串的集合。

由于两种语言都是图灵可判定的，这意味着每种语言都有这样的算法。您需要证明，使用这些算法，您可以获得一种新的算法来确定交叉点中字符串的成员资格。

提示:当且仅当字符串同时具有两种语言时，该算法才会回答yes。