Decidability

A decision problem asks for a yes-or-no answer on a specified class of inputs. Examples include whether a nonnegative integer is even and whether a given finite automaton accepts a given string. Encoding the positive instances as strings turns the problem into a formal language.

The problem is decidable if an algorithm always halts and answers correctly. Passing selected tests is not enough, and a program that never returns has not supplied a negative answer. Finite-automaton acceptance is decidable: simulate the transitions on the finite input, then inspect the final state.

References: [1]

Semidecidability, also called recognizability, guarantees eventual acceptance of every positive instance but allows rejection or endless computation on negative instances. For the halting problem, the input describes a program and its input. Simulation confirms a positive instance when the program finishes. Continued waiting cannot establish that it will never finish.

If both a problem and its complement are recognizable, they are decidable. Interleave the two recognizers, allowing each a finite number of steps at a time, until one accepts. Every input belongs to exactly one side, so this procedure eventually obtains the answer. Merely searching for one kind of evidence lacks that guarantee.

References: [2]

The halting problem is undecidable for arbitrary programs and inputs. This rules out a uniformly correct, always-terminating algorithm; it does not prevent analysis of individual programs. A program that immediately returns plainly terminates. A fixed loop with no exit may plainly run forever. Correctly classifying these examples does not furnish a general method.

Undecidability proofs can use diagonal arguments or reductions from established undecidable problems. A reduction supplies an effective conversion: a decision algorithm for the target problem would also decide the original one, contradicting the known result. Failure to invent an algorithm is not itself such a proof.

References: [2]

Computability asks whether a method exists in principle; complexity investigates the resources it requires. An exhaustive procedure can establish decidability while being impractical. For example, whether a finite list has a subset summing to a target can be decided by testing every subset. Each test is finite and there are finitely many tests, although their number grows rapidly with the list. With the list 2, 5, 9, a target of 7 has the witness 2 plus 5. A target of 8 has none, which can be established by checking all eight subsets, including the empty subset. The procedure establishes both outcomes, not only successful searches.

An open question describes the state of knowledge, whereas undecidability requires a result about a specified computational model and input domain. Practical tools may restrict the permitted programs, impose a resource bound, or answer 'unknown' in some cases. These can be useful choices without providing a decision procedure for the original unrestricted problem.

References: [3]