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

1.3k Views Asked by At

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?

1

There are 1 best solutions below

4
On BEST ANSWER

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.