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?
8
$\begingroup$
$\endgroup$
-
1$\begingroup$ This means the machine should stay on the same spot, no moves. There are not many possibilities for such a computation? $\endgroup$ – Hendrik Jan Sep 13 '15 at 10:16
-
$\begingroup$ It might move, actually. But then suppose that $\delta(q_0,\_) = (q,a,D)$ for some state $q$, label $a$ and $D\in\{L,R\}$. What can you say about the case $q\neq q_0$? What happens next if $q = q_0$? $\endgroup$ – Klaus Draeger Sep 13 '15 at 20:05
-
2$\begingroup$ This problem might be decidable. I found this paper hal.inria.fr/inria-00074105 (I didn't read so I'm not sure) that could interest you. It claims that the halting problem for one state Turing machine is decidable. (which is a problem fairly close to your problem). $\endgroup$ – wece Nov 13 '15 at 16:29
-
1$\begingroup$ Please change the title of the question "... when start tape is blank" if your bounty is about "any tape input": the case in which the tape is balnk is trivially decidable (I posted an answer but I suddenly deleted it when I saw the comment on the bounty) $\endgroup$ – Vor Nov 29 '16 at 19:18
4
+50
$\begingroup$
$\endgroup$
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.
-
$\begingroup$ I don't understand this answer/algorithm. Consider a TM that does have a transition rule that can leave state $s_0$ if the symbol under the head is X. Now we need to know whether X can ever be present in any cell of the tape. Suppose the TM also has transition rules on state $s_0$ that move left and/or right and write symbols to the tape, including potentially X. Now what are you going to do? How are you going to tell whether the TM can potentially write X onto some cell and then revisit that cell? I don't see any algorithm here that handles that situation. $\endgroup$ – D.W.♦ Nov 28 '16 at 17:05
-
2$\begingroup$ @D.W. Are we talking about deteministic or nondeterministic TM here? $\endgroup$ – Eugene Nov 28 '16 at 18:29
-
$\begingroup$ That's a question you should ask the original poster if you think it is unclear, but with the information given I think we should assume a deterministic TM. That said, I suspect I was influenced by the bounty text, which referred to ~"never leaves the initial state no matter for any initial state of the tape"~, which is a bit different from "never leaves the input state when the initial state of the tape is all-blank", so perhaps my objection is irrelevant to the question as posed. $\endgroup$ – D.W.♦ Nov 30 '16 at 1:53
-
$\begingroup$ Anyway, perhaps it would help to justify the "easy to see..." part more carefully. For instance, you don't seem to explicitly use the fact that the initial tape is all blank, even though it appears that this makes a big difference. $\endgroup$ – D.W.♦ Nov 30 '16 at 1:56
3
$\begingroup$
$\endgroup$
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.
