Answer : A,B,C.

$L_4 = \{ \langle M \rangle \mid M \text{ is a Turing Machine and} \,\, M \text{ takes more than } 1073 \text{ steps on every string} \} $

$L_4$ is decidable as we can have a systematic procedure(algorithm, which terminates in some finite amount of time for every input) in deciding whether a given Turing machine $M$ takes more than 1073 steps on every string.

For $L_4$ we have to monitor for at most $\textsf{TM}$ for $1073+1$ steps for all possible inputs of size $<=1073$ (if the input set is having $k$ alphabets, we will have finite number of such possible strings which we need to inspect on the input Turing Machine.) Let’s call all these strings of length $<=1073$ as the “candidate strings” (candidates for inspection on the input TM)(So, we have finite number of candidate strings)

Our algorithm takes Turing Machine as input.

If for all the candidate strings, Input Turing Machine $M$ is taking more than $1073$ steps, then it means for all larger strings(strings of length $>1073$) also $M$ must take more than $1073$ steps and we(our algorithm) can answer “yes” for input $M.$

If for at least one of the candidate strings, Input Turing Machine $M$ is halting in less than or equal to $1073$ steps, then we(our algorithm) can answer “No” for input $M.$

So, we can decide, for any input Turing machine $M,$ whether $M$ takes more than 1073 steps on every string Or whether $M$ halts in less than or equal to 1073 steps on at least one string.

Thus we(our algorithm) correctly decided $L_4.$

So, Problem in Option D is Decidable.

NOTE :

For Option D, we cannot apply Rice Theorem as the property mentioned in the Problem of Option D, is about the Turing machine and not about the language. Rice Theorem is applicable only for the languages of Turing Machines.

$L_1 :$

Option 1 is the “Equivalence Problem of Turing Machines” which asks to Decide whether two TMs accept the same language. This is equivalent to the problem of whether two programs compute the same output for every input. This is standard undecidable problem.

Though, we cannot apply Rice Theorem for $L_1$ as Rice Theorem is applicable only when input is a single Turing Machine and the problem to be decided is related to language of this Turing Machine.

$L_2 :$

Option 2 is the “Regularity Problem of Turing Machines” which asks to Decide whether the language accepted by the given TM is a regular language. This is standard undecidable problem. We can also apply Rice Theorem for $L_2$. $L_2$ is undecidable using Rice Theorem because “language of Turing machine” being Regular is Non-trivial property of “languages of TM”. In simple terms, language of TMs is RE language and “being regular” is Non-Trivial Property of RE languages. As per Rice Theorem, ALL Non-trivial properties of RE languages are Undecidable.

**Examples of undecidable problems :**

• About Turing machines:

– Is the language accepted by a TM empty, finite, regular, or context-free?

– Does a TM meet its “specification,” that is, does it have any “bugs.”

• About context-free languages:

– Are two context-free grammars equivalent?

– Is a context-free grammar ambiguous?

$L_3 :$

Option 3 is the “Universaility/Completeness Problem of Turing Machines” which asks to Decide whether the TM accepts all strings or not. This is standard undecidable problem. We can also apply Rice Theorem for $L_3$. $L_3$ is undecidable using Rice Theorem because “language of Turing machine” being $\Sigma^*$ is Non-trivial property of “languages of TM”. In simple terms, language of TMs is RE language and “being $\Sigma^*$” is Non-Trivial Property of RE languages. As per Rice Theorem, ALL Non-trivial properties of RE languages are Undecidable.