0
$\begingroup$

Given a TM M, will it ever reach any other state other than start state if it starts with blank tape ? Is the above problem decidable ?

I think that if a TM really reaches any other state other than start state then we can check the transitions and find out. But if it doesn't at any point of time then we can't say that it will never reach other state in future too so it results in infinite waiting.

So the problem is undecidable or R.E according to me but the answer is decidable.

Please tell me where am I going wrong .

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael♦ Nov 12 '17 at 21:15
3
$\begingroup$

Say $M$ has start state $s$ and transition function $\delta$. Construct a new Turing machine $M'$ with $Q = \{s, HALT\}$ (where s != HALT) and $\delta'$ as it's transistion function, defined by the following. $s$ is again the start state and $HALT$ is the accept state.

$$ \delta'(s, x) = \begin{cases} s & \delta(s, x) = s \\ HALT & \mbox{otherwise} \\ \end{cases} $$

$M'$ will halt IFF $M$ ever transitions out of the start state.

If you know what the maximum shifts function is for two states and your symbols then you can simulate $M'$ for that many steps to determine if $M'$ halts or not. Non constructively even if we can't compute the busy beaver function for your number of symbols it has some value and therefore our argument still goes through.

This shows that, at least classically speaking, this problem is decidable. It also constructively shows that it's decidable for any number of symbols that we can constructively prove an upper bound on the maximum step function for. This algorithm runs in constant time...where the constant might be very large. So asymptotically it's ideal. I'm not sure if there's an algorithm that does this with a smaller constant but I'm betting it's not possible.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you please explain it in some way ? I am not aware of these functions. $\endgroup$ – Sagar P Nov 13 '17 at 5:40
  • $\begingroup$ I think reading the Wikipedia page that I linked would be a good introduction. I also realize that I messed up the last paragraph. I'll edit that. The just of what I'm saying is that you can simulate your Turing machine for a certain number of steps and if it doesn't transition out of the start state in that number of steps then it never will. That number is the maximum shifts function for 2 states and the number of symbols your using in your TM. $\endgroup$ – Jake Nov 14 '17 at 7:51
  • $\begingroup$ Oh and if you meant transition functions then transition functions are discussed here: en.wikipedia.org/wiki/Turing_machine $\endgroup$ – Jake Nov 14 '17 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.