0
$\begingroup$

Please confirm if my understanding of the below question, and my answer is correct.

Is the following language decidable? Justify your answer.

$L = \{\langle M_1,M_2\rangle \mid L(M_1) \cup L(M_2) = \Sigma^*\}$

The source of this question is a past exam paper from Warwick University.

My interpretation of the question is:

There are two 'machines' M1 and M2 which both define a language. The union of those two languages (which is L) accepts all possible words.

My current thinking is that L is decidable because I can construct an algorithm (M3) that accepts a word and passes it concurrently to both M1 and M2. Because every word must be accepted by either M1 or M2 (or both) at least one of the machines should halt with an accept at some point. As soon as this happens M3 halts with an accept. Therefore because M3 halts on all inputs, L is decidable.

Please let me know if my understanding is correct.

Thanks.

Improve this question
$\endgroup$
6
  • $\begingroup$ Why should one of the machines $M_1$ or $M_2$ halt if $\langle M_1, M_2\rangle\notin L$? $\endgroup$ Commented Jun 1, 2024 at 14:06
  • $\begingroup$ @Nathaniel probably I have misunderstood the question. Part of my struggle is understanding what the angled brackets around M1/M2 mean in this context. $\endgroup$ Commented Jun 1, 2024 at 14:16
  • 1
    $\begingroup$ Where did you encounter this question, then? Why are you trying to solve it if you don't even understand the objects you are manipulating? $\endgroup$ Commented Jun 1, 2024 at 14:31
  • 1
    $\begingroup$ A small hint: The language $\texttt{ALL}_{TM} = \{\langle M \rangle : M \text{ is TM s.t. } L(M) = \Sigma^*\}$ is undecidable. What would a positive answer to your question imply for $\texttt{ALL}_{TM}$? $\endgroup$ Commented Jun 1, 2024 at 15:15
  • $\begingroup$ @Nathaniel The question is from a past exam paper and complete. This is no other context other than other unrelated questions. The fuller explanation is I am trying to help a friend's child with the material as her course tutors/professors were crap. I did the same course a couple of decades ago but have forgotten most of the details so am relearning it with her. $\endgroup$ Commented Jun 1, 2024 at 15:51

1 Answer 1

Reset to default
2
$\begingroup$

Part of my struggle is understanding what the angled brackets around M1/M2 mean in this context.

Indeed, you are correct. The question is: given two Turing machines $M_1,M_2$ can we decide whether together they accept all strings. Since we need to have $M_1,M_2$ as input to an algorithm (i.e., some other Turing machine) we will have to write down these machines. Thus we list states and transitions in some binary form. The result of this is called the encoding of $M_1,M_2$ and is denoted as $\langle M_1,M_2 \rangle$. The precise format of the encoding is usually not specified. It should in some sense be reasonable. It should have an adequate length and not give away the answer to the question.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thankyou for clarifying the question. So my answer is irrelevant as I have misunderstood the question. $\endgroup$ Commented Jun 1, 2024 at 15:56

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.