# Tag Info

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