I want to determine whether this decision problem is decidable. I have tried to establish reductions from Halt and "Accepts empty-string", but I've not yet found a solution.
Can someone help me out?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityI want to determine whether this decision problem is decidable. I have tried to establish reductions from Halt and "Accepts empty-string", but I've not yet found a solution.
Can someone help me out?
I would say it is decidable.
If I understood correctly, here's what I think.
First of all a TM starts from some initial state $s_0$. How can it change the state? In your transition function you have something like $(s_0, x) \to (s_i, y, m)$ where $s_i$ is a state and $x$, $y$ are symbols and $m$ is the head move (left right or stay). So, if it leaves the initial state there should be a transition from $(s_0, \_)$ to some state not $s_0$. Easy to see that it is if and only if. Thus, you can construct another Turing machine which has the input as a TM in some encoding, goes through the transition function and checks the condition above, and the problem is decidable.
Trivially decidable. Given the tape is truly blank, then T in state $s_0$ must change the currently-scanned tape cell and do one of three things: (1) Transition to a different state and move left or right (or halt); (2) Transition back to $s_0$ and move one cell left; (3) Transition back to $s_0$ and move one cell right. For both (2) and (3) the TM head has moved away from the original tape cell and is now scanning a blank cell; therefore it is now in the same situation that it started in, and will act the same way. So for (2) or (3) the TM behavior on a blank tape is to move forever in one direction, leaving a trail of (probably) altered cells. So this property can be checked by inspecting the contents of a single row of the TM's 'program' (i.e the transition rule for $s_0$ scanning blank) - if the new state is NOT $s_0$ (including 'halts') the answer is YES, otherwise the answer is NO.
I am also reasonably certain that the problem is still decidable given arbitrary input - you just have to pay closer attention to which direction the tape head moves depending on the current cell contents.