search
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

  3. GAITONDE

    348 Points

  4. Vimal Patel

    87 Points

  5. Shaik Masthan

    38 Points

  6. BLACK_CLOUD

    14 Points

  7. sekhar_1621

    13 Points

  8. OgbeborBeatrice

    13 Points

  9. RAMYA.F

    9 Points

  10. vkw1111

    9 Points

0 votes
29 views

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
Yes

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
0
Then what about state entry problem?
0

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 ?

Similarly...here 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.

0
both are same, right??
0
No ...state entry problem is undecidable.
0
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?
0
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.
2
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
0

@Arjun Sir

Can u tell me, if reasoning of C) is correct here https://gateoverflow.in/20404/tifr2011-b-25

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

...