Register

GO Classes DPP | TOC|DECIDABILITY

265 views
3 3 votes

Let $L_1=\left\{\langle M\rangle \mid M\right. \text{ is a TM that halts on every input of the form} \left.0^n 1^n\right\}$.

Which of the following is true about $L_1$ ?
 

  1. $L_1$ is recursive
     
  2. $L_1$ is recursively enumerable but not recursive
     
  3. The complement of $L_1$ is recursively enumerable but $L_1$ is not
     
  4. Neither $L_1$ nor its complement is recursively enumerable

2 Answers

2 2 votes

The set "halts on all $0^n 1^n$" requires universal quantification over infinitely many strings; you cannot semidecide that property or its complement.

Simulation on all $0^n 1^n$ cannot confirm non-halting for any one string within finite time → neither side is r.e.

0 0 votes
$$\boxed{\text{D. Neither }L_1\text{ nor }\overline{L_1}\text{ is recursively enumerable};\quad L_1\notin RE,\;\overline{L_1}\notin RE}$$

$$
\begin{aligned}
L_1 &: M\text{ halts on every }0^n1^n
\;\rightarrow\; \text{universal condition}
\;\rightarrow\; L_1\notin RE,\\
\overline{L_1} &: M\text{ doesn't halt on at least one }0^n1^n
\;\rightarrow\; \text{non-halting cannot be verified}
\;\rightarrow\; \overline{L_1}\notin RE.
\end{aligned}
$$
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | TOC...Next → · GO Classes DPP | TOC...
← Previous in category · GO Classes DPP | TOC...Next in category → · GO Classes DPP | TOC...
Position:
Show:

Related questions

1 1 vote
1 1 answer
276
276 views
GO Classes asked Nov 18, 2025
276 views
GO Classes DPP | TOC|DECIDABILITY
Let $L_1$ and $L_2$ be two regular languages accepted by DFAs $M_1$ and $M_2$, respectively.Consider the following problems:P1: "Is $L_1 \cap L_2=\emptyset$ ?"P2: "Is $L_...
3 3 votes
1 1 answer
303
303 views
GO Classes asked Nov 18, 2025
303 views
GO Classes DPP | TOC|COUNTABILITY
Let$$S=\{\langle M, w\rangle \mid M \text { is a Turing machine that halts within }|w| \text { steps on input } w\} .$$Is the set $S$ countable or uncountable? Countable,...
3 3 votes
1 1 answer
270
270 views
GO Classes asked Nov 18, 2025
270 views
GO Classes DPP | TOC|CFG
Consider the following context-free grammars:$$\begin{aligned}& G_1: S \rightarrow a S|B, B \rightarrow b B c| \epsilon \\\\& G_2: S \rightarrow a S b|C, C \rightarrow b ...
3 3 votes
2 2 answers
370
370 views
GO Classes asked Nov 18, 2025
370 views
GO Classes DPP | TOC|CFG
Consider the following context-free grammars:$$\begin{aligned}& G_1: S \rightarrow a S|S b| \epsilon \\& G_2: S \rightarrow a S b|a A, A \rightarrow a A| \epsilon\end{ali...