3

Your example almost works. You need to make sure that the regular part is disjoint from the non-decidable part. Suppose our alphabet has at least two symbols, say $a$ and $b$. Consider any undecidable langauge $H$, for example the halting set, and define $$L_2 = \lbrace b w \mid w \in H\rbrace$$ and $$L_1 = L_2 \cup \lbrace a \rbrace.$$ Now it is obvious ...


2

$L = \{\text{<M, k>| M is a Turing Machine and } |w \in L(M) : w \in a^*b^*| \geq k \}$ Now we want to find whether $L$ is $RE$ or not. Yes, indeed your interpretation of language $L$ is wrong. $L$ is a language of strings of form $\langle M, k \rangle$ where $M$ is turing machine which accepts atleast $k$ strings of form $a^*b^*$. So, now it's ...


2

Just take for $L_2$ an undecidable language of $a^*$ and take $L_1 = L_2 \cup \{b\}$. Then $L_2$ is also undecidable and $L_2 - L_1 = \{b\}$ is regular.


2

As you suspected, it can happen that $L_1-L_2\not=a^*$. The assumption that $H$ does not contain $a^*$ does not imply that $\lnot H$ must contain $a^*$. For example, if $H\cap a^*= \{a^2\}$, then $\lnot H$ does not contain $a^2$, let alone $a^*$. The technique to arrive at a simple solution is to let the regular part be disjoint with $L_2$. Here is the ...


2

Its obvious why a semi-decidable language is verifiable ($w$ would be the machine's computation history on $x$). Now, we will show the other way: Let $V(x,w)$ be a verifier for $L$. Define $M(x)$ as the following algorithm: Let $S$ be an empty array (of turing machine emulations) For every $w\in\Sigma^*:$ Add a new emulation of $V(x,w)$ to $S$. For every ...


2

There are a few ways to approach this. You can use a counting argument to show that for every $A$ there exists $B$ such that $B\nleq_T A$. Let $L_A=\{B| B\le_T A\}$ denote the set of all languages reducible to $A$. Show that $f:L_A\rightarrow \mathbb{N}$ that maps languages $B\in L_A$ to $n$ such that $M_n$ is a reduction from $B$ to $A$ is an injection, and ...


1

For $L_1:$ It's not decidable. Define $C=\{A_TM\}$. Now, by Rice's theorem we have that the language $L=\{<M>|L(M)\in C\}$ is undecidable. (By the extended theorem it's not even semi-decidable.) But notice $L_1=L$ and therefore $L_1$ is undecidable. For $L_2:$ It's decidable, although your solution is not correct. Notice that $\overline{A_TM}$ is not ...


1

I think you can force the enumeration to be only on machines with a very strict format: a hard-coded poly time "clock" at the start, and after that the rest of the TM. This will allow you to check in poly time (not even requiring a verifier) whether a given string $p$ is a part of the enumeration


1

It's only semi-decidable if you word your decision problem very carefully. And you have to word it in such a way that the case where both programs never reach their $n$s is in the REJECT category. Since $\infty < \infty$ is ambiguous/undefined I would explicitly mention this case in your decision problem. Other than that, yes it's correct. Your machine ...


1

Q1: A state can get repeated. The point is that if a state gets repeated and no non-empty symbol has even been written, then you known the that the Turing machine will never halt as it is necessarily stuck cycling through some of the states encountered so far. Since none of the states of the cycle caused the TM to write a non-blank symbol, the TM will never ...


1

A language is Turing decidable if you can write a C program (replace C with your favorite programming language) that outputs YES if the input belongs to the language and outputs NO otherwise. It is Turing recognizable if in the latter case the C program simply never halts.


1

An undecidable language is necessarily infinite. A finite subset of it is always trivially decidable.


Only top voted, non community-wiki answers of a minimum length are eligible