Awesome q2a theme
0 votes

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

in Theory of Computation by (8 points) | 41 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.
by (4.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.

0 votes
0 votes
by (1.2k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Feb 2020
  1. shashin

    363 Points

  2. Shaik Masthan

    79 Points

  3. SuvasishDutta

    39 Points

  4. srestha

    33 Points

  5. Mk Utkarsh

    32 Points

  6. neeraj_bhatt

    31 Points

  7. !KARAN

    30 Points

  8. Debapaul

    23 Points

  9. Pratyush Priyam Kuan

    18 Points

  10. kalra05

    18 Points

Monthly Top User and those within 60% of his/her points will get a share of monthly revenue of GO subject to a minimum payout of Rs. 500. Current monthly budget for Top Users is Rs. 75.
3,324 questions
1,581 answers
89,913 users