The halting problem cannot be solved in the general case. It is possible to come

Question

The halting problem cannot be solved in the general case. It is possible to come up with defined rules that restrict allowed inputs and can the halting problem be solved for that special case?

For example, it seems likely that a language that does not allow loops for instance, would be very easy to tell if the program would halt or not.

The problem I'm trying to solve right now is that I'm trying to make a script checker that checks for the validity of the program. Can halting problem be solved if I know exactly what to expect from script writers, meaning very predictable inputs. If this cannot be solved exactly, what are some good approximation techniques to solve this?

Explanation / Answer

Yes, it can be possible. One common way of solving such problems is considering an extra (monotone) uncomputable parameter depending of the code as a part of input. The complexity of the problem having that parameter can be severely reduced.

We cannot compute the parameter, but if you know that the input instances you are dealing with have small parameter values, you can fix it to a small number and use the algorithm.

This and similar tricks are used in formal-methods to deal with undecidability of halting and similar problems. But if what you want to decide is complicated, the complexity of your algorithms is unlikely to be better than running the algorithm on those instances.

Regarding the other question, if you restrict the inputs enough, then the halting problem can be come easy. For example, if you know that the inputs are polynomial time algorithms, deciding the halting problem for them is trivial (since every polynomial time algorithm halts).

Problems that arise in formal-methods are typically undecidable, you may want to check the literature on how they deal with these problems in practice.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.