41 views

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

| 41 views

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.
by (4.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.