18
$\begingroup$

Let $F = \{⟨M⟩:\text{M is a TM which stops for every input in at most 50 steps}\}$. I need to decide whether F is decidable or recursively enumerable. I think it's decidable, but I don't know how to prove it.

My thoughts

This "50 steps" part immediate turns the R sign for me. If it was for specific input it would be decidable. However, here it's for every input. Checking it for infinite inputs makes me think that the problem is co-RE, i.e. its complement is acceptable.

Perhaps, I can check the configurations and see that all configurations after 50 steps don't lead to accept state- how do I do that?

|cite|improve this question
$\endgroup$
21
$\begingroup$

Let's consider the more general problem of machines which stop after at most $N$ steps, for some $N \geqslant 1$. (The following is a substantial simplifcation of a previous version of this answer, but is effectively equivalent.)

As swegi remarks in an earlier response, if the machine stops after at most $N$ steps, then only the cells $0,1,\ldots,N-1$ on the tape are significant. Then it suffices to simulate the machine $M$ on all input strings of the form $x \in \Sigma^N$, of which there are a finite number.

  • If any of these simulations fail to enter a halting state by the $N^{\text{th}}\:\!$ transition, this indicates that any input string starting with $x$ is one for which the machine does not stop within the first $N$ steps.
  • If all of these simulations halt by the $N^{\text{th}}\:\!$ transition, then $M$ halts within $N$ steps on all inputs of any length (of which the substring of length $N$ is all that it ever acts on).
|cite|improve this answer
$\endgroup$
  • $\begingroup$ And- Do I assume that $x$ such that its length is longer than $N$ is automatically being rejected? $\endgroup$ – Jozef Aug 9 '12 at 15:20
  • $\begingroup$ Why Can't it jumps to any further than N cell within the N steps of computing? $\endgroup$ – Jozef Aug 9 '12 at 15:27
  • $\begingroup$ @Jozef: the simulations just iterate through all possible input strings of length N. You could iterate through more strings, but you won't learn anything more, because only the first N symbols matter anyway. The reason why it can't go any further than N cells is because Turing machines (or the standard definition of them anyway) only move one cell per step. $\endgroup$ – Niel de Beaudrap Aug 9 '12 at 15:28
  • $\begingroup$ Right, I got it. so you mind only the first N symbols of every word, thus you check all the combinations of them. why did you delete the configurations description? $\endgroup$ – Jozef Aug 9 '12 at 15:41
  • $\begingroup$ It's still visible if you look at the previous edits. I revised it to this because while the other answer was maybe interesting, a lot of what made it "interesting" only served to obscure the fact that the decision procedure is nothing more or less than simulating $M$ on all possible inputs of length $N$. I thought it better to revise the answer to something much more straightforward, and which basically got to the root of what makes the problem decideable. $\endgroup$ – Niel de Beaudrap Aug 9 '12 at 15:43
4
$\begingroup$

If $M$ stops in no more than 50 steps, than the positions $M$ can reach on the normally infinite tape are limited. Thus the infinite tape can be simulated by a finite one. This means that the tape can be simulated by a finite automaton. It follows that a turing machine $M$ that stops in no more than 50 steps is bisimilar to some finite automaton $M'$.

Let $Q$ be the set of states of $M$, $F \subset Q$ the set of accepting states and $\Gamma$ be the alphabet. Then we build the set of states $Q'$ of $M'$ as follows: $Q' = \{ \langle n, q, s, p, a\rangle \, | n \in \{0,...,50\} \, q \in Q, s \in \Gamma, p \in \{-50,...,50\}, a \equiv q \in F\}$ where $p$ is the position of the read/write head above the tape. We can restrict the position to $\{-50,...,50\}$ because the number of allowed computing steps limits the number of reachable positions.

Having a state $\langle n, q, s, p, a\rangle$ of the finite automaton $M'$ then means that we are at state $q$ of the original automaton, with $s$ on the tape at position $p$ where also the read/write head is positioned, after the $n$-th computing step. The state is an accepting one if $a \equiv true$.

Transforming the transition relation of a concrete turing machine is a little more work but not necessary for the original question, because it is enough to show that the state space is finite (and thus we can just test each input with a length of at most 50 symbols on each such automaton). The idea is to build a new transition relation that goes from a state $\langle n, q, s, p, a \rangle$ to a state $\langle n+1, q', s', p', a'\rangle$ in the $n$-th computing step iff the transition $\langle q, s, p\rangle \rightarrow \langle q', s', p'\rangle$ was in the original transition relation.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ How do you simulate the storage on the tape, i.e. the ability to revisit symbols you have already read, on a finite automaton? $\endgroup$ – Niel de Beaudrap Aug 9 '12 at 13:14
  • $\begingroup$ @NieldeBeaudrap: You enumerate the whole state space, i.e. you do model checking of the finite tape and the turing machine's control automaton. $\endgroup$ – swegi Aug 9 '12 at 15:36
  • 1
    $\begingroup$ Given that the OP is asking basic questions of computability for Turing Machines, you might want to unpack that sketch into something fuller. (I myself have never heard the phrase "model checking" in a computational context before.) In context, I would typcially assume by 'finite automaton' you would mean a DFA or similar unless you specified otherwise, and it's not clear to me what would correspond to the input of the DFA in such a construction. If you just mean a graph representing possible trajectories of the TM, then I agree. $\endgroup$ – Niel de Beaudrap Aug 9 '12 at 15:40
  • $\begingroup$ With model checking the finite part of the tape I basically mean what you have written in your answer: just test each input of size at most 50 and check whether an accepting state is reached. $\endgroup$ – swegi Aug 9 '12 at 21:05
  • 1
    $\begingroup$ I wish people would stop propagating the myth that a Turing machine tape needs to be infinite. It doesn't - it can be finite as long as it is extended as needed. $\endgroup$ – reinierpost Oct 6 '14 at 16:19

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.