# TM decidability using pigeonhole principle

I think since the input word is delimited by special symbols, which the machine cannot move past, the language accepted by such a device should be finite. We know that all finite languages are regular, and regular languages are decidable by a TM. Does it make sense for answering the question?

• It's not true in general that the language is finite -- only that every word in it is of finite length, meaning that it's possible to construct a longer word (e.g., by appending a letter). Similarly, the set of natural numbers is infinite, but any particular natural number $i$ is finite (e.g., we can always construct a larger natural number $i+1$). – j_random_hacker Mar 31 at 1:15
• Can you check my logic to answer this question? – Juns Mar 31 at 1:50
• If the head passes the k-th cell, update k accordingly, and we accept. Therefore, the language accepted by this Turing machine is decidable because the machine on input w that is a subset of L eventually halts by accepting or rejecting w. – Juns Mar 31 at 1:53
• "If the language accepted by such a device is decidable" -- I don't think it's ever useful to start out by assuming the thing you're trying to prove. OTOH it's often useful to assume the opposite, with the goal of showing a contradiction. "then the Turing machine should halt by accepting or rejecting" -- you mean a full TM, not the read-only kind, right? "Thus, if the Turing machine is in a loop (if it detects cycles in the TM), it should reject" -- which TM is in a loop? What is "it" in "it detects cycles"? – j_random_hacker Mar 31 at 3:12
• You have edited the question to remove all mention of the read-only TM -- why? Now the final sentence, "Does it make sense for answering the question?", doesn't make sense. – j_random_hacker Mar 31 at 12:37

I think since the input word is delimited by special symbols, which the machine cannot move past, the language accepted by such a device should be finite. We know that all finite languages are regular, and regular languages are decidable by a TM. Does it make sense for answering the question?

You can easily simulate any DFA in your model, and so your model accepts all regular languages. In particular, it also accepts some infinite languages, for example the language of all words.

Your class of machines is two-way finite automata, and it is known to accept the regular languages, that is, it coincides in power with one-way finite automata such as DFAs and NFAs.

However, that is not the answer that the setter had in mind. Rather, imagine the working of such a machine, having $$m$$ states, on an input word of length $$n$$. The head could be in $$n+2$$ different positions, and consequently the machine can be in $$(n+2)m$$ different configurations. Therefore, after that many steps, either the machine has halted (either accepting or rejecting the input), or some configuration has repeated (by the pigeonhole principle), in which case the machine is in an infinite loop, and will never accept. Hence after $$(n+2)m$$ steps we can already tell the fate of the input.

• Can you verify my logic to answer this question below? – Juns Mar 31 at 8:06
• The language accepted by such a device is decidable, which means that the Turing machine can halt (either accepting or rejecting the input), or be in a loop because some configuration has repeated (by the pigeonhole principle). We reject when the machine is in a loop. If the machine runs more steps than the possible number of configurations, by the pigeonhole principle it entered the same configuration twice. Hence, the machine is in a loop, and we can safely reject. Also, we count configurations according to k, where k is the leftmost cell reached so far by the head. – Juns Mar 31 at 8:10
• If the head passes the k-th cell, update k accordingly, and we accept it. Therefore, the language accepted by the one-tape Turing machine is decidable because the machine on the input w [ L eventually halts by accepting or rejecting w. – Juns Mar 31 at 8:11
• I'm not sure what it means to "count configurations according to $k$". At any rate, the reasoning is outlined in my answer, and it is close to what's in your comments. – Yuval Filmus Mar 31 at 8:16
• The idea is that you can predict whether the Turing machine will accept the word based on the first so many steps. The prediction depends on the semantics of the original Turing machine. – Yuval Filmus Mar 31 at 8:27