this question is inspired by a recent popular question [1] on a boundary relating to decidable and undecidable problems (ie open problems in this area), a sort of counterpoint.

there are at least some papers of a type that attack multiple instances of undecidable problems. each instance of the general problem is not known a priori to be decidable or undecidable, and the paper describes strategies/techniques for identifying/sorting some into decidable cases, and provides algorithms which decide the problem if it is found to be among the decidable cases.

what are papers of this genre, systematically attacking multiple instances of undecidable problems?

[1] A simple problem whose decidability is not known / Reyzin, tcs.se


2 Answers 2


Let's say an algorithm A solves a "special case" of the decision problem L if on input x, $A(x)$ always either outputs the correct answer $L(x)$, or outputs "?".
These algorithms (which may be randomized) are sometimes called "errorless heuristics" and have been studied in complexity theory, esp. average-case complexity; see e.g. this paper of Watson and references therein.

A basic question you can ask about a very difficult decision problem is whether it contains any nontrivial easy cases. E.g. if L is decidable, is there any (deterministic) errorless heuristic A for L that solves $L(x)$ on infinitely many inputs? This has been explored in the notion of immunity (along with co-immunity, bi-immunity, simplicity and others) in computability theory. See e.g. this wiki article. Complexity-theoretic analogues have been studied as well.

Since you mention multiple instances, I might also interpret the question as looking for research into algorithms which, given instances $x^1, \ldots, x^m$ for a decision problem (i.e. language) L, compute some partial information about the membership/nonmembership of the given strings in $L$.

One of the earliest and most influential works of this type was by Jockusch, who in his dissertation and this 1968 paper defined "semi-recursive" languages. L is semi-recursive if there is a computable "selector" function that, given instances $x^1, x^2$, selects one of these two strings as being "logically more likely" to lie in L. That is, we require that whenever at least one of $x^1, x^2$ lie in L, the string selected by the selector lies in L.

The study of polynomial-time analogues of this concept was initiated by Selman in this 1979 paper. Since then there has been tons of work on "p-selective" languages (the polytime version of semi-recursive languages) along with "membership comparable" languages and many other related concepts. I can't summarize all this work, but consult e.g. this article of Beigel, Fortnow, and Pavan, and this book of Hemaspaandra and Torenvliet. The concept of bounded queries in computability and complexity is also related, see this survey by Gasarch.


The obvious candidates for these kinds of things are number theoretical.

  1. The collatz problem springs to mind, see What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?. The cited article is here, but it is about tag systems rather than number theory.

  2. Termination is, of course, undecidable, but of course there are some nice algorithms that capture realistic classes of terminating systems. In particular this paper by Ben Amram gives a neat criterion in which one can decide whether a program is a) polynomial or b) non-terminating, by finding a bound such that, if the program terminates, then it does in less than that bound.

  3. The problem of finding solutions of integer polynomial equations is, as is well-known, undecidable, but for large classes of problems we do know the solution. See here https://mathoverflow.net/questions/51987/which-types-of-diophantine-equations-are-solvable, or here for instance. The criteria for decidability are generally rather simple in this case and will typically depend on the degree of the equation and some algebraic relation on the coefficients. I don't know whether checking this can be called a "decision procedure".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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