Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
In computer science and automata theory, a state is a unique configuration of information in a program or machine. It is a concept that occasionally extends into some forms of systems programming such as lexers and parsers....
of a computer program whose value is monotonically decreased with respect to a (strict) well-founded relation
Well-founded relation
In mathematics, a binary relation, R, is well-founded on a class X if and only if every non-empty subset of X has a minimal element with respect to R; that is, for every non-empty subset S of X, there is an element m of S such that for every element s of S, the pair is not in R:\forall S...
In most computer programming languages, a while loop is a control flow statement that allows code to be executed repeatedly based on a given boolean condition. The while loop can be thought of as a repeating if statement....
In computer science, a loop invariant is an invariant used to prove properties of loops. Informally, a loop invariant is a statement of the conditions that should be true on entry into a loop and that are guaranteed to remain true on every iteration of the loop...
In computer science, a termination analysis is program analysis which attempts to determine whether the evaluation of a given program will definitely terminate. Because the halting problem is undecidable, termination analysis cannot work correctly in all cases. The aim is to find the answer...
. A loop variant whose range is restricted to the non-negative integers is also known as a bound function, because in this case it provides a trivial upper bound on the number of iterations of a loop before it terminates. However, a loop variant may be transfinite
Transfinite number
Transfinite numbers are numbers that are "infinite" in the sense that they are larger than all finite numbers, yet not necessarily absolutely infinite. The term transfinite was coined by Georg Cantor, who wished to avoid some of the implications of the word infinite in connection with these...
, and thus is not necessarily restricted to integer values.
A well-founded relation is characterized by the existence of a minimal element of every non-empty subset of its domain. Therefore
The existence of a variant proves the termination of a while loop
While loop
In most computer programming languages, a while loop is a control flow statement that allows code to be executed repeatedly based on a given boolean condition. The while loop can be thought of as a repeating if statement....
Transfinite induction is an extension of mathematical induction to well-ordered sets, for instance to sets of ordinal numbers or cardinal numbers.- Transfinite induction :Let P be a property defined for all ordinals α...
. (See also , pp. 32–33, 174–176.) A basic property of a well-founded relation is that it has no infinite descending chain
Infinite descending chain
Given a set S with a partial order ≤, an infinite descending chain is a chain V that is a subset of S upon which ≤ defines a total order such that V has no least element, that is, an element m such that for all elements n in V it holds that m ≤ n.As an example, in the set of integers, the chain...
s. Therefore a loop possessing a variant will terminate after a finite number of iterations, as long as its body terminates each time.
In most computer programming languages, a while loop is a control flow statement that allows code to be executed repeatedly based on a given boolean condition. The while loop can be thought of as a repeating if statement....
, or, more generally, a computer program that may contain while loops, is said to be totally correct if it is partially correct and it terminates.
Rule of inference for total correctness
In order to formally state the rule of inference for the termination of a while loop we have demonstrated above, recall that in Floyd–Hoare logic, the rule for expressing the partial correctness of a while loop is:
where I is the invariant
Loop invariant
In computer science, a loop invariant is an invariant used to prove properties of loops. Informally, a loop invariant is a statement of the conditions that should be true on entry into a loop and that are guaranteed to remain true on every iteration of the loop...
, C is the condition, and S is the body of the loop. To express total correctness, we write instead:
where, in addition, V is the variant, and by convention the unbound symbol z is taken to be universally quantified
Universal quantification
In predicate logic, universal quantification formalizes the notion that something is true for everything, or every relevant thing....
.
Every loop that terminates has a variant
The existence of a variant implies that a while loop terminates. It may seem surprising, but the converse is true, as well, as long as we assume the axiom of choice: every while loop that terminates (given its invariant) has a variant. To prove this, assume that the loop
terminates given the invariant I where we have the total correctness assertion
Consider the "successor" relation on the state space induced by the execution of the statement S from a state satisfying both the invariant I and the condition C. That is, we say that a state is a "successor" of if and only if
I and C are both true in the state and
is the state that results from the execution of the statement S in the state
We note that for otherwise the loop would fail to terminate.
Next consider the reflexive, transitive closure of the "successor" relation. Call this iteration: we say that a state is an iterate of if either or there is a finite chain such that and is a "successor" of for all i,
We note that if and are two distinct states, and is an iterate of , then cannot be an iterate of for again, otherwise the loop would fail to terminate. In other words, iteration is antisymmetric, and thus, a partial order.
Now, since the while loop terminates after a finite number of steps given the invariant I, and no state has a successor unless I is true in that state, we conclude that every state has only finitely many iterates, every descending chain with respect to iteration has only finitely many distinct values, and thus there is no infinite descending chain
Infinite descending chain
Given a set S with a partial order ≤, an infinite descending chain is a chain V that is a subset of S upon which ≤ defines a total order such that V has no least element, that is, an element m such that for all elements n in V it holds that m ≤ n.As an example, in the set of integers, the chain...
, i.e. loop iteration satisfies the descending chain condition.
Therefore—assuming the axiom of choice—the "successor" relation we originally defined for the loop is well-founded
Well-founded relation
In mathematics, a binary relation, R, is well-founded on a class X if and only if every non-empty subset of X has a minimal element with respect to R; that is, for every non-empty subset S of X, there is an element m of S such that for every element s of S, the pair is not in R:\forall S...
on the state space since it is strict (irreflexive) and contained in the "iterate" relation. Thus the identity function on this state space is a variant for the while loop, as we have shown that the state must strictly decrease—as a "successor" and an "iterate"—each time the body S is executed given the invariant I and the condition C.
Moreover, we can show by a counting argument that the existence of any variant implies the existence of a variant in ω1, the first uncountable ordinal
First uncountable ordinal
In mathematics, the first uncountable ordinal, traditionally denoted by ω1 or sometimes by Ω, is the smallest ordinal number that, considered as a set, is uncountable. It is the supremum of all countable ordinals...
, i.e.,
This is because the collection of all states reachable by a finite computer program in a finite number of steps from a finite input is countably infinite, and ω1 is the enumeration of all well-order
Well-order
In mathematics, a well-order relation on a set S is a strict total order on S with the property that every non-empty subset of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded strict total order...
In mathematics, especially in set theory, two ordered sets X,Y are said to have the same order type just when they are order isomorphic, that is, when there exists a bijection f: X → Y such that both f and its inverse are monotone...
on countable sets.
Practical considerations
In practice, loop variants are often taken to be non-negative integer
Integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s, or even required to be so, e.g. , but the requirement that every loop have an integer variant removes the expressive power of unbounded iteration from a programming language. Unless such a (formally verified) language allows a transfinite proof of termination for some other equally powerful construct such as a recursive function call
Recursion (computer science)
Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. The approach can be applied to many types of problems, and is one of the central ideas of computer science....
The primitive recursive functions are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions...
. Ackermann's function is the canonical example of a recursive function that cannot be computed in a loop with an integer variant
For loop
In computer science a for loop is a programming language statement which allows code to be repeatedly executed. A for loop is classified as an iteration statement....
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
, however, functions that are not primitive recursive lie far beyond the realm of what is usually considered tractable
Tractable
Tractable may refer to:*Operation Tractable, a military operation in Normandy 1944*Tractability concerning how easily something can be done...
. Considering even the simple case of exponentiation as a primitive recursive function, and that the composition of primitive recursive functions is primitive recursive, one can begin to see how quickly a primitive recursive function can grow. And any function that can be computed by a Turing machine
Turing machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
in a running time bounded by a primitive recursive function is itself primitive recursive. So it is difficult to imagine a practical use for full μ-recursion where primitive recursion will not do, especially since the former can be simulated by the latter up to exceedingly long running times.
Kurt Friedrich Gödel was an Austrian logician, mathematician and philosopher. Later in his life he emigrated to the United States to escape the effects of World War II. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the...
Gödel's incompleteness theorems are two theorems of mathematical logic that establish inherent limitations of all but the most trivial axiomatic systems capable of doing arithmetic. The theorems, proven by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of...
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
imply that there are while loops that always terminate but cannot be proven to do so; thus it is unavoidable that any requirement for a formal proof of termination must reduce the expressive power of a programming language. While we have shown that every loop that terminates has a variant, this does not mean that the well-foundedness of the loop iteration can be proven.
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
, of an integer variant computed from some upper bound on the number of iterations remaining in a while loop. However, C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
allows side effects in the evaluation of expressions, which is unacceptable from the point of view of formally verifying a computer program.
unsigned int B; /* computes a loop iteration bound without side effects */
unsigned int V = B; /* set variant equal to bound */
assert(I); /* loop invariant */
while (C) {
assert(V > 0); /* this assertion is the variant's raison d'être */
S; /* body of loop must not alter V */
V = min(B, V - 1); /* variant must decrease by at least one */
}
assert(I && !C); /* invariant is still true and condition is false */
Why even consider a non-integer variant?
Why even consider a non-integer or transfinite variant? This question has been raised because in all practical instances where we want to prove that a program terminates, we also want to prove that it terminates in a reasonable amount of time. There are at least two possibilities:
An upper bound on the number of iterations of a loop may be conditional on proving termination in the first place. It may be desirable to separately (or progressively) prove the three properties of
partial correctness,
termination, and
running time.
Generality: considering transfinite variants allows all possible proofs of termination for a while loop to be seen in terms of the existence of a variant.
In most computer programming languages, a while loop is a control flow statement that allows code to be executed repeatedly based on a given boolean condition. The while loop can be thought of as a repeating if statement....
In computer science, a loop invariant is an invariant used to prove properties of loops. Informally, a loop invariant is a statement of the conditions that should be true on entry into a loop and that are guaranteed to remain true on every iteration of the loop...
Transfinite induction is an extension of mathematical induction to well-ordered sets, for instance to sets of ordinal numbers or cardinal numbers.- Transfinite induction :Let P be a property defined for all ordinals α...
In the mathematical discipline of set theory, there are many ways of describing specific countable ordinals. The smallest ones can be usefully and non-circularly expressed in terms of their Cantor normal forms. Beyond that, many ordinals of relevance to proof theory still have computable ordinal...
Correctness (computer science)
Weakest-preconditions of While loop
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
induced by the execution of the statement S from a state satisfying both the invariant I and the condition C. That is, we say that a state 
is a "successor" of 
if and only if
for otherwise the loop would fail to terminate.
is an iterate of 
if either 
or there is a finite chain 
such that 
and 
is a "successor" of 
for all i, 
and 
are two distinct states, and 
is an iterate of 
, then 
cannot be an iterate of 
for again, otherwise the loop would fail to terminate. In other words, iteration is antisymmetric, and thus, a partial order.
since it is strict (irreflexive) and contained in the "iterate" relation. Thus the identity function on this state space is a variant for the while loop, as we have shown that the state must strictly decrease—as a "successor" and an "iterate"—each time the body S is executed given the invariant I and the condition C.
and
is the state that results from the execution of the statement S in the state 