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