I have a question of terminology regarding algorithms.
I cannot distinguish very well these three concepts : correctness, soundness and completeness.
From what I understand, if my algorithm gives me a result that it was supposed to give me, then it is a sound algorithm. First question, what is the difference with correctness ?
Also, if each possible result that my algorithm should give me is actually given by it, then it is a complete algorithm (I'm not sure about this one, so consider it as a second question).
In my particular case, I actually have an algorithm that satisfies the two properties above. I did the proof, but I would like to characterize this proof (i.e., something like "Proof – Soundness and completeness of Algorithm $A$) and I'm a bit embarrassed…
Thank you for your help !
Best Answer
Let's say we want to find primes by certain algorithms (called primality tests)
A sound primality test will never say that a number is prime when it is composite (but it may fail to detect some primes as such; it may also sometimes fail to HALT)
A complete primality test will never say that a number is composite when it is prime (but it may fail to detect some composites, thus produceing "pseudo-primes" or it fails to HALT)
A paritally correct primality test may sometimes fail to give an result at all (i.e., fail to HALT). But if it returns a result it is correct: If it says prime, the input is prime, and if it says composite, the input is composite.
A (totally) correct primality test will always halt, and it will always return the correct answer.