GO Classes CS Test Series | Mock GATE | Test 4 | Question: 37

Answer 1

Option A Explanation:

It is a standard Undecidable problem if a given TM $M$ prints a symbol $\#$ or not.

Assume that You can decide if a given TM $M$ when run on a given $w$ will print a symbol $\#$ or not. 

Now, I come to you to decide the Halting Problem. 

You can do this: Given a TM $M$, you can change it a little bit. Just make small changes so that if $M$ halts then it prints a symbol $\#$, otherwise it does not print $\#$.

Now, if you can decide problem of printing $\#$, then you can also decide the halting problem. 

That's the reduction from halting problem to the printing $\#$ problem.

• A. Undecidable, since the halting problem is reducible to it. Indeed, given $\text{M}$ (without $\#$ among the tape alphabet) build $\text{M}^{\prime}$ as follows: $\text{M}^{\prime}$ simulate $\text{M}$ but each time $\text{M}$ wants to halt $\text{M}^{\prime}$ first prints $\#$ and then halts. It is clear, that $\text{M}$ halts on $y$ if and only if $\text{M}^{\prime}$ writes $\#$ on input $y$. Therefore, if we could decide (A) we would be able to decide the halting problem.
   
• B. Decidable. This is a trivial property, since for each $\text{TM M}$ there are infinitely many $\text{TMs}\;\text{M}^{\prime}$ accepting the same r.e. set $\text{A = L(M)}$.
   
• C. Undecidable. Acceptance problem of $\text{TMs}.$
   
• D. Decidable. Run $\text{TM M}$ for max $2023$ steps on all strings of length $\leq 2023.$

Detailed Video Explanation of Option D Here: ALL Step Based GATE PYQs & Complete Explanation 

 

Option D Explanation:  https://gateoverflow.in/396348/go-classes-cs-test-series-2025-mock-gate-test-2-question-37?show=439558#c439558

Comments

@pranavbhosle_, that's correct analogy. 

@kritika madaan, Assume that You can decide if a given TM $M$ when run on a given $w$ will print a symbol $\#$ or not. 

Now, I come to you to decide the Halting Problem. 

You can do this: Given a TM $M$, you can change it a little bit. Just make small changes so that if $M$ halts then it prints a symbol $\#$, otherwise it does not print $\#$.

Now, if you can decide problem of printing $\#$, then you can also decide the halting problem. 

That's the reduction from halting problem to the printing $\#$ problem.

---

In simple words, it is a standard Undecidable problem if a given TM $M$ prints a symbol $\#$ or not.

---

@Deepak Poonia sir how is option C decidable here ? is it not the equality problem of RE languages?

---

@Chaitanya_Kamasani here we can think of different turing machines accepting the same language L but with different encodings 
So there are infinitely many turing machines accepting the same RE language

Answer 2

 

• A. Undecidable: This is a variation of the "State Entry Problem" or "Halting Problem." We cannot generally determine if a TM will ever perform a specific action (like writing a symbol) on an input.

• B. Decidable (Trivial): For any recursively enumerable (r.e.) set, there are always infinitely many TMs that accept it (e.g., by adding redundant states). A decider for this problem would simply always output "Yes."

• C. Undecidable: This is the Membership Problem ($w \in L(M)$), which is known to be undecidable.

• D. Decidable: This is a bounded property. To check if $M$ takes $> 2023$ steps on some input, we only need to check inputs up to length 2023. If an input is longer, the TM cannot even read past the 2023rd symbol within 2023 steps. Since the number of strings of length $\leq 2023$ is finite, we can simulate the TM on all of them for 2024 steps. If it hasn't halted on any, the answer is "Yes."

Correct Options: B and D.

---