2
The notion of an "undecidable program" doesn't make sense, for the same reasons I gave in response to your last question. It makes sense to talk about whether a language is decidable or undecidable. It doesn't make sense to talk about whether a program is decidable or undecidable. If you check the formal definition of decidable, you'll see that ...
1
Here's another, elementary proof technique that does not use Rice's theorem which is way overkill for this simple problem.
We have Turing machine family $F(A)$ that goes into an infinite loop for any input except 2, in which case it will run program $A$, which can be arbitrary.
Now if we could decide your original problem we could decide for arbitrary ...
1
Because the problem HALT defined in the online source is different from yours. Their HALT is defined as:
\begin{align}
\{ \langle M, w\rangle \mid{} &M\text{ is a Turing machine, $w$ is a string,}\\
&\text{and $M$ }accepts\text{ $w$ after a finite computation}\}
\end{align}
1
Yes. Remember that $A\subseteq B$ just means "every element of $A$ is also an element of $B$." In case $A=\emptyset$, this is trivially true ("vacuously true") regardless of what $B$ is.
It may also help to think in terms of counterexamples: $A\subseteq B$ is the "default" situation, and is only false if there is a counterexample: some $x\in A$ with $x\not\...
1
Elucidium addresses most of your question; let me address the remaining point, which is why $\emptyset$ and $L_\emptyset$ behave differently.
The point is that they're simply very different sets in the first place. For example, $\emptyset$ has no elements - that's its definition - while $L_\emptyset$ is infinite (there are lots of Turing machines which don'...
1
By definition, a language $L$ is decidable if there exists a TM $M\mid L = L(M)$ deciding it. Consider a TM that rejects on all inputs (for example, one where $q_o = q_{\text{rej}}$). The language of this TM is $\emptyset$, so $L=\emptyset$ is decidable.
With reductions, in general if $A\leq B$ ($A$ reduces to $B$), then $B$ is at least as hard as $A$ with ...
Only top voted, non community-wiki answers of a minimum length are eligible
