Log In
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Sep 2019
  1. Satbir

    567 Points

  2. Bikram

    566 Points


    348 Points

  4. Vimal Patel

    87 Points

  5. Shaik Masthan

    38 Points


    14 Points

  7. sekhar_1621

    13 Points

  8. OgbeborBeatrice

    13 Points

  9. RAMYA.F

    9 Points

  10. vkw1111

    9 Points

0 votes

Is it decidable that a Turing Machine will ever leave the start state on any input?

in Theory of Computation 7 points 29 views

3 Answers

0 votes

We can see the transitions which are defined for the starting state and could tell what will happen when we give input

.i.e. whether it would leave the starting state and go to other state or would keep looping in the starting state only.
2.1k points
Then what about state entry problem?

State entry problem is whether we will ever enter a given state or not.

Now if i say whether we would start from starting state or not then it will not be state entry problem right ? we need to check whether it would leave the starting state or not.

and since it is the starting state only so we can check using the transitions which are given for the machine whether it would ever leave the starting state or not.

both are same, right??
No ...state entry problem is undecidable.
yes, both the problems are not the same but the logic of your answer can be applied to both right?

And, in a TM can we get “infinite sequence” of moves without changing the states?
yes we can have infinite sequence of moves without changing the states.

Sir, so can we can that we can reduce the given problem to state entry problem and since state entry problem is undecidable so thats thats why the given problem is also undecidable.
But how will you do that reduction?

Simpler way to answer is – see if “infinite sequence of moves” are possible or not and based on it say if the problem is decidable

@Arjun Sir

Can u tell me, if reasoning of C) is correct here

I stuck how reduction is performing here?? Plz. check it.