Definition
Sound Algorithm
A algorithm is sound if every conclusive result it returns is correct. Given a validity relation
and an algorithm where
denotes an inconclusive result, soundness requires For a decision predicate
, the one-sided forms are sound acceptance and sound rejection: An algorithm is unsound when some conclusive result is false; merely being inconclusive is permitted. Conclusiveness asks whether the algorithm always answers, while soundness asks whether its answers are correct. This is the algorithmic analogue of a sound calculus.