If we have a primitive CPU/computer with small amount of registers and/or RAM, it is easy to check if the program will loop endlessly: just write down all registers/RAM cells states at each state and wait for repeating one. If we reached repeating state, we got to know that the program will loop inifinitely and will never terminate. We just need a CPU/computer with bigger RAM for the task.

If so, does it mean that halting problem exists only for TM with infinite tape/RAM, so it is not possible to write down all tape states?


closed as off-topic by user6973, David Eppstein, Kaveh, Yuval Filmus, Mohammad Al-Turkistany May 10 '16 at 6:56

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Community, David Eppstein, Kaveh, Yuval Filmus, Mohammad Al-Turkistany
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ See cs.stackexchange.com/q/32845 $\endgroup$ – Kaveh May 9 '16 at 3:39
  • $\begingroup$ You are correct. A TM with a fixed amount of tape is equivalent to a finite automaton. You can directly map its configurations (internal states plus tape contents) to the states of a FM. $\endgroup$ – reinierpost May 9 '16 at 7:55
  • 1
    $\begingroup$ Even for a counter machine equipped with only 2 (unlimited) numeric counters (and no tape) the Halting problem is undecidable (see counter machines ) $\endgroup$ – Marzio De Biasi May 9 '16 at 14:59

"Easy to check" is the understatement of the century: can you actually carry out your proposed plan of "just" writing down all the registers/RAM cells, etc? You're right that it takes finite time, but a large amount of finite time. Our best algorithms for performing this check are exponential in the size of the input on the tape, and a strong version of the $P\neq NP$ conjecture states that there is no algorithm that achieves a faster (subexponential) runtime uniformly over all inputs.

So the P=NP problem is a finitary version of the halting problem. The latter has no algorithmic solution when input length is unbounded. The former admits a brute-force solution, but the amount of time required to find it is so large that for all practical purposes it's as good as unsolvable.

Edit: My statement that the halting problem can't be decided by any algorithm because the "input length is unbounded" is inaccurate, since for DFAs the latter also holds but the languages they accept are of course decidable. But certainly when the number of configurations is finite -- as is the case for a finite-tape TM -- a brute-force search solves the halting problem. Somewhat confusingly, the finiteness of the number of configurations is actually not necessary for decidability, as the DFA example shows.

  • $\begingroup$ I don't understand your final comment: DFAs are almost by definition the deterministic model of computation with only finitely many configurations... $\endgroup$ – Joshua Grochow May 9 '16 at 16:15
  • $\begingroup$ Which definition of "configuration" do you use? In my definition, a configuration is an ordered pair $(q,u)$ where $q$ is a state (i.e., the current one) and $u$ is the suffix of the input not yet read by the DFA. Thus, a configuration is (in general) the minimal amount of information required to compute the final state of the DFA. Because $u$ lives in an infinite set, the number of configurations is infinite. The number of states is finite of course. $\endgroup$ – Aryeh May 9 '16 at 17:25
  • $\begingroup$ If you fix the input string then the number of configurations is also finite. So for every input string we have a bound (which is computable). Any model where this holds halting will be decidable. $\endgroup$ – Kaveh May 10 '16 at 18:05
  • $\begingroup$ If you limit the input length then you only have a finite number of possible languages in any formalism. $\endgroup$ – Aryeh May 10 '16 at 18:34

One way of looking at this is saying that since the state space is so large -- even if finite -- then treating it as infinite is a valid approximation. But I think that there's a better way to look at this which gives a sense of the problem. When finite domains are concerned, instead of looking at the canonical halting problem, we should consider the bounded halting problem (see, e.g., the time and space hierarchy theorems; while the space version is more suitable for your problem description, we'll look at the time version, as it's a bit simpler), sometimes also called SHORT DTM (whereas the space-restricted version is sometimes called COMPACT DTM), and ask ourselves the following question: given a TM $M$, an input $x$ and a natural number $t$, what is the worst-case complexity of telling whether $M$ halts on input $x$ in under $t$ steps? Using a diagonalization proof nearly identical to that of the original halting problem, we can see that we cannot answer the question in under $t$ states. I.e. there is no algorithm more efficient than the brute-force one you've described.

You can then ask, if we can work really hard once but then answer the question efficiently (i.e. in less than the actual running time) for all inputs for a machine $M$. More formally, we can ask whether for every machine $M$, there exists a natural constant $k$ such that given $M$ and any inputs $x_1, ..., x_k$ we can tell whether $M$ halts on each of them in under $t$ steps and do so efficiently, i.e. in under $k \cdot t$ steps? The answer to that is, similarly, no. Proof: take the universal TM as $M$ and see that if we could answer the question efficiently we'd get a contradiction with bounded halting.

Interestingly, these two proofs don't require true diagonalization, i.e. they don't require that we can really simulate the UTM, only that we're able to simulate it for up to $t$ steps, so this result is rigorous even for so called "total functional" languages, that can't interpret themselves. A little more thought would show what this result truly means: we cannot answer any question (a la Rice's theorem) about a TM (even a total one) in less time the the number of states it has (or the number of states we're interested in). We can say that the complexity for answering a non-trivial question about a TM (even a total one) is $\Omega(|S|)$, where $S$ is the set of states. This result happens to be so rigorous that it applies to virtually all computation models, even DFAs (with some exceptions, I think, for PDA). For an overview of results in the finite-state case, see this survey paper by Schnoebelen.


Not the answer you're looking for? Browse other questions tagged or ask your own question.