1
$\begingroup$

(Decidable or not?) Formulate the following problem as a language: Given a Turing machine $M$ and a string $w$, determine whether $M$ visits each of its states exactly once during the computation with input string $w$. Prove your answer.

So the problem above is what I am trying to solve. I am looking for a general direction to solve this so far this is what I am thinking but I may be completely wrong.

My Thoughts: This problem is decidable because the Turing machine can have a list of all possible paths ,$E^*$, and we could check $E^*$ to ensure that each state was visited once and only visited once within the computation. However this doesn't seem like nearly enough and I am not sure what direction to head.

$\endgroup$
1
  • $\begingroup$ Given a Turing machine, M, that has multiple states, m, we know that if M terminates after m steps then it has visited every state exactly once. If we take another machine M’ that takes on a pair (M,w) where M is a Turing machine and w is the input that M takes on. We can simulate M on M’. We run M on w and in doing so we can count the number of states that it visits. M’ job is to determine whether the number of states visited is equal to m. If it is equal to m then accept, if it is not equal to m then reject. my question now is would this be enough to prove that this is decidable $\endgroup$ Dec 2 '16 at 22:13
1
$\begingroup$

Hint: If a Turing machine has $m$ states and it visits each of them exactly once, then it terminates after $m$ steps.

$\endgroup$
5
  • $\begingroup$ What about loops? I see what your saying but would I say that it terminates after m or more steps as opposed to just m? Nevermind I wrote this and then thought about the question that it has to visit them exactly once $\endgroup$ Dec 2 '16 at 21:24
  • $\begingroup$ It's just a hint – you'll have to solve the problem on your own. $\endgroup$ Dec 2 '16 at 21:25
  • $\begingroup$ Okay thanks! Wasn't asking for the solution just trying to clarify. I have exams next week so not trying to just get answers trying to understand. $\endgroup$ Dec 2 '16 at 21:25
  • $\begingroup$ can you look at my new solution and tell me what you think ? $\endgroup$ Dec 2 '16 at 22:10
  • $\begingroup$ Unfortunately this is not how this site works. I suggest contacting your TA. $\endgroup$ Dec 2 '16 at 22:35

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.