Invariant (computer science)

From Wikipedia, the free encyclopedia

In computer science, a predicate that will always keep its truth value throughout a specific sequence of operations, is called (an) invariant to that sequence.

Contents 1 Use 2 Example 3 References 4 See also

[edit] Use

Although computer programs are typically mainly specified in terms of what they change, it's equally important to know or specify the invariants of a program. This is especially useful when reasoning about the program. The theory of optimizing compilers, the methodology of design by contract, and formal methods for determining program correctness, all pay close attention to invariants in computer programs.

Programmers often make use of assertions in their code to make invariants explicit. Some object oriented programming languages have a special syntax for specifying class invariants.

[edit] Example

The MU puzzle is a good example of a logical problem where determining an invariant is useful. The puzzle:

1. If a string ends with an I, a U may be appended (MxI → MxIU)
2. Any string after an M may be completely duplicated (Mx → Mxx)
3. Any three consecutive Is (III) may be replaced with a single U (MxIIIy → MxUy)
4. And two consecutive Us may be removed (MxUUy → Mxy)

Is it possible to convert MI into MU using these four transformation rules only?

One could spend many hours applying these transformation rules to strings. However, it might be quicker to find a predicate that's invariant to all rules, and makes getting to MU impossible. Logically looking at the puzzle, the only way to get rid of any Is is to have three consecutive Is in the string. The only way to get rid of all Is is when there are exactly three consecutive Is. This makes the following invariant interesting to consider:

The number of Is in the string is not a multiple of 3.

This is an invariant to the problem if for each of the transformation rules the following holds: if the invariant held before applying the rule, it will also hold after applying it. If we look at the net effect of applying the rules on the number of Is and Us we can see this actually is the case for all rules:

Rule	#Is	#Us	Effect on invariant
1	+0	+1	Number of Is is unchanged. If the invariant held, it still does.
2	×2	×2	If n is not a multiple of 3, then 2 × n isn't either. The invariant still holds.
3	-3	+1	If n is not a multiple of 3, n - 3 isn't either. The invariant still holds.
4	+0	-2	Number of Is is unchanged. If the invariant held, it still does.

Above table shows clearly that the invariant holds for each of the possible transformation rules. Which basically means that whichever rule we pick, at whatever state, if the number of Is was not a multiple of three before applying the rule, it won't be afterwards either.

Given that there is a single I in the starting string MI, and one is not a multiple of three, it's impossible to go from MI to MU as zero is a multiple of three.

[edit] References

[edit] See also

• Hoare logic
• Loop invariant
• Object invariant
• Const correctness