Deciding TM which fails to halt whenever the length of its input string is a prime number

Question

I have the following Statement:

"A TM called $A$ which fails to halt (i.e runs forever) whenever the length of its input string is a prime number, and eventually halts for all other input strings"

Is the language recognized by $A$ is decidable?

Answer 1

The machine $A$ does quite a job of deciding its own language, so to speak. The only part where $A$ fails to decide its language is when the input has length $n$ wherer $n$ is a prime number. Thus, to decide the language of $A$, one only has to:

• check if the input size is a prime number. If this is the case, reject the input.
• if the input size if a composite number, launch $A$ on the input.

Why does this machine decide $L(A)$?

Suppose that $w\in L(A)$. Then by definition, $w$ has size a composite number and is so that $A$ accepts on input $w$. As our algorithm answers with the same answer as $A$, this algorithm accepts $w$.

Suppose now that $w\not\in L(A)$. If $w$ is rejected by $A$ (meaning $A$ halts and rejects), then $w$ is also rejected by our algorithm, by definition. If $A$ does not halt on $w$, it is because $w$ has length a prime number, so that we are in the first case of our algorithm, and $w$ is rejected.

Hence, our machine accepts $w$ iff $w\in L(A)$, hence it decides $L(A)$.