3,998 views

Which of the following is/are undecidable?

1. Given two Turing machines $\textit{M}_{1}$ and $\textit{M}_{2},$ decide if $\textit{L(M}_{1}) = \textit{L(M}_{2}).$
2. Given a Turing machine $\textit{M},$ decide if $\textit{L(M)}$ is regular.
3. Given a Turing machine $\textit{M},$ decide if $\textit{M}$ accepts all strings.
4. Given a Turing machine $\textit{M},$ decide if $\textit{M}$ takes more than $1073$ steps on every string.

1. Given two Turing machines M1 and M2, decide if $L(M1)=L(M2)$. → Equivalence Problem of TM (Undecidable
2. Given a Turing machine M, decide if $L(M)$ is regular → Regularity Problem of TM (Undecidable)
3. Given a Turing machine M, decide if M accepts all strings → Completeness Problem of TM (Undecidable
4. Given a Turing machine M, decide if M takes more than $1073$ steps on every string → Decidable (just check for <= $1074$ steps)

@Abhrajyoti00 adding some explanation to the 4th option.

First, we need to observe that strings which are having a length of more than 1073 will take more than 1073 steps. So we just need to check for strings which are having lengths less than 1073 because they may or may not take more than 1073 steps.

How many such strings are there?

answer: Finite (depends on $\sum$ )

So, we can check for all those strings till 1073 + 1 step can answer yes/no.

$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 :
– 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.”
– 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.

why are the candidate strings the ones of length less than 1073 ?

https://youtu.be/CFRiAIsUPUY after @24:10 here you mention that there should be immediately otherwise it will be undecidable.

How can we say that

1. Given a Turing machine M, decide if M takes more than 1073 steps on every string.

It is Decidable as it not explicitly mentioning that M takes immediately more than 1073 steps.

Which of the following two makes sense, English wise?

1. Immediately after
2. Immediately more than

Immediately after but as here it’s given more than so no need to worry whether immediately given or not “Is that so”?

Option A : Given two Turing Machines M1 and M2, decide if L(M1) = L(M2).

That means, “ Language accepted by M1 and M2 are same. “ – is this decidable problem ?

So, we need to check every string from the universal language , either accepted by (M1 and M2) or rejected by (M1 and M2).

We may have, string ‘w’  which is not belongs to L, can be rejected by M1, can cause looping in M2.

In this situation, we need to wait for infinite time. Therefore given problem is undecidable.

option B : Given Turing Machine M, decide if L(M) is regular.

Standard Undecidable problem.

Option C : Given Turing Machine M, decide if M accepts all strings

let suppose, if given M is accepting all strings, then it have process all the strings which will take infinite amount of time.

I mean, after completion of one string ( it should produce yes due to M accepts all strings ), I will give one more string and this process will continue Infinite times because i have infinite strings. So I can’t say M accepts all strings with in finite amount of time.

Therefore Undecidable problem.

Option D : Given Turing Machine M, decide if M takes more than 1073 steps on every string.

For every string, M will run 1073 steps on strings whose length less than 1073 and decide it. However whose string length is morethan 1073, obviously takes more than 1073 steps.