Prove decidability of language in logic

Question

Let $S$ be a non-empty finite alphabet, Let $S^\ast$ denotes the set of words that can be written using the given alphabet. Let $A_1, A_2 \subseteq S*$ be languages such that membership in each of $A_1, A_2$ is decidable. Prove membership in the following language is decideable: $$A_1 \cap A_2 = \{w \in S^\ast | w \in A_1 \land w \in A_2\}$$

Can someone provide a hint? Sounds like the halting problem.

Answer 1

How would one decide if a string is in $A_1$ and $A_2$? First, is it in $A_1$? If so, is it also in $A_2$? If so, it is a member of the intersection, otherwise not. Do we have a decision procedure for a string being in $A_1$? (Yes, $A_1$ is decidable.) Do we have a decision procedure for a string being in $A_2$? (Yes, also decidable.) Can we combine two decision procedures so that the result is positive only if both procedures declare membership?

This can initially be hard to work with because the two decision procedures are unnamed. Let's start by fixing that. (Much progress just comes from labelling the parts that are on the table in front of us.) The rest then follows the line of thought above.

Since membership in $A_1, A_2$ is decidable, there are \begin{align*} d_1 &: S^* \rightarrow \{\text{Member}, \text{Nonmember}\} \\ d_2 &: S^* \rightarrow \{\text{Member}, \text{Nonmember}\} \text{,} \end{align*} which decide whether a given string is a member of $A_1, A_2$, respectively. Then the function \begin{align*} f &: S^* \rightarrow \{\text{Member}, \text{Nonmember}\} \\ &: s \mapsto (d_1(s) = \text{Member}) \wedge (d_2(s) = \text{Member}) \end{align*} decides the language $A_1 \cap A_2$. You should show that the finite conjunction of decision procedures meets your definition of a decision procedure.

Note: There are a large number of specifications of "decision procedure". You may have to adapt details of the above to match your setting.

Answer 2

We have a Turing machine $T_1$ that halts on every input and outputs $0$ or $1$ (or goes to one final state (accepting state) or another (rejecting state), depending on what your text's conventions are) that determines membership of $A_1$.
Likewise $T_2$ for $A_2$.

Now just do both of them at the same time in a combined Turing machine (a product or some such construction), and accept if both accept.