Does the Halting Problem apply when evaluating programs that are regular languages?

Here is my understanding of the Halting Problem: It is impossible to write a program H that can determine for any arbitrary program P that P will halt on input I.

Suppose we restrict the problem. Instead of "any arbitrary program" we restrict P to programs that are regular languages; does the halting problem still apply?

Is it possible to write a program H which can determine for any program P that is a regular language that P will halt on input I?

Is it possible to write a program H which can determine for any program P that is a context-free language that P will halt on input I?

• What does it mean for a program to be a language? – Chris Eagle Mar 23 '13 at 23:32

Before getting to the questions themselves, we must be more careful about the definitions. The Halting problem takes as input a machine $M$. How we interpret machine can be quite generous of course, a Turing Machine is the basic example, but talking about something closer to reality, TMs are programs (the computer is a Universal TM).

Machines aren't languages, they generate/recognise/compute/decide/... languages. So the formulation you have where a program is a regular language is a little confused.

If we rephrase the questions, then we can make some headway. If the machine $M$ we are given is a DFA then $HALT_{M}$ is decidable. In fact, the answer is just YES. DFAs always halt. If we get a NFA or a regular expression, then we can use the conversion algorithm to get a DFA, so we know they always "halt" (a slightly odd term for REs of course). One of the key things to notice is that DFAs always consume one symbol from the input at each step, so we always reach the end, and thus the machine always halts.

Jumping ahead further, we can even decide $HALT_{LBA}$ - as an LBA has a bounded amount of space to work in, there are a finite number of configurations it can go through, so we can just run it long enough and either it will halt by that time, or it never will.

As PDAs are less powerful than LBAs, we also get $HALT_{PDA}$ is decidable (note that in any accepting computation on a PDA, the stack cannot grow larger than a bounded function of the length of the input).

So in this sense the answer to both your questions is yes. However if we are not as generous with the information we are given, then things get harder. In particular, given a TM $M$ it is even undecidable whether $L(M)$ is regular. So if we are given just a TM, then we're doing no better, even though the language it recognises is regular, we simply can't check it.

• Thank you very much Luke, this is very helpful. You wrote: If the machine M we are given is a DFA then HALT M is decidable. What machine is M given to? That is, what machine decides that M will halt? Is it a TM (e.g., a computer) that is used to decide that M will halt? If yes, then a TM (which we cannot determine that it will halt) is used to decide that a PDA will halt; how can we be sure that the TM will halt and tell us that the PDA will halt? Sorry to be so confused about this. This topic is so fascinating to me. – Roger Costello Mar 24 '13 at 9:24
• @user68196, it's a good question. When say a language is decidable (in this case variations on the halting problem in particular), we mean there is a Turing Machine that decides it (a decider). So how do we know that this TM halts? Well, at the high level, it's defined that way, so a decider always halts. In principle this could be done non-constructively, but normally we construct a TM that decides the language, so we can prove that that particular TM always halts. – Luke Mathieson Mar 24 '13 at 9:58
• (part 2) This exposes a subtlety in the Halting Problem, although we can't decide $HALT_{TM}$ in general, for some TMs we can prove that they always halt (or sometimes don't or never halt). – Luke Mathieson Mar 24 '13 at 9:59
• Thanks again Luke. This is excellent information. – Roger Costello Mar 24 '13 at 11:21