Virtual Gate Test Series: Theory Of Computation - Turing Machine

Question

Consider the following two decision problems

• A. Whether a Turing machine takes more than $481$ steps on input $\epsilon?$
• B. Whether a Turing machine accepts the null string $\epsilon?$

 Which of the following statements is true$?$

1. Problem $A$ is decidable but $B$ is not
2. Problem $A$ is undecidable but $B$ is decidable
3. Both $A$ and $B$ are decidable
4. Both $A$ and $B$ are undecidable

Answer 1

A)  is correct.Check out this https://drona.csa.iisc.ernet.in/~deepakd/atc-2011/tm-more-undecidable.pdf

Comments

thks bro..

Answer 2

We simply implement our turing machine exact 448 step and see whether it accept given string w and we got answer in the form of yes or no.Therefore clealry it is halting turing machine therefore it is decidable.

But in the case of epsilonturing machine does not accept epsilon therefore we can not say anyhting for its decidability.