# Dictionary Definition

correctness

### Noun

2 conformity to social expectations [ant:
incorrectness]

# User Contributed Dictionary

## English

### Etymology

### Noun

- Freedom from error.
- Conformity to the truth or to fact.
- Conformity to recognized standards.
- The state of an algorithm that correctly mirrors its specification.

#### Translations

freedom from error

- Czech: správnost
- Finnish: virheettömyys

# Extensive Definition

In theoretical computer
science, correctness of an algorithm is asserted when it
is said that the algorithm is correct with respect to a specification.
Functional correctness refers to the input-output behaviour of the
algorithm (i.e., for each input it produces the correct output).
See also program
verification.

A distinction is made between total correctness,
which additionally requires that the algorithm terminates, and
partial correctness, which simply requires that if an answer is
returned it will be correct. Since there is no general solution to
the halting
problem, a total correctness assertion may lie much
deeper.

For example, if we are successively searching
through integers 1, 2,
3, … to see if we can find an example of some phenomenon
— say an odd perfect
number — it is quite easy to write a partially
correct program (use integer
factorization to check n as perfect or not). But to say this
program is totally correct would be to assert something currently
not known in number
theory.

A proof would have to be a mathematical proof,
assuming both the algorithm and specification are given formally.
In particular it is not expected to be a correctness assertion for
a given program implementing the algorithm on a given machine. That
would involve such considerations as limitations on memory.

A deep result in proof
theory, the Curry-Howard
correspondence, states that a proof of functional correctness
in constructive
logic corresponds to a certain program in the lambda
calculus. Converting a proof in this way is called program
extraction.

In auditing, correctness is one of
the
financial statement assertions that has to be ensured. For
example, an auditor has to ensure a transaction is correctly
recorded in the books. For recording a purchase, he or she has to
check the posting to accounts payable and purchase account, gross
amount, amount of discount received from supplier.

See also: Murray Dougall

## See also

correctness in German: Korrektheit
(Informatik)

correctness in Japanese: 正当性
(計算機科学)