
646
Maher
On the other hand, logical equivalence of programs is not stronger than
equivalence of completions: {A B) and {A B; A A} are logically
equivalent but their completions are not.
Often we wish to use a program as part of a larger program. To express the
fact that two programs will perform identically as subprograms we define, for
each equivalence ~ defined above, that two programs P
{
and P
2
are equivalent
as program segments iff P
{
Ug-^ U Q for every finite program Q. Clearly
any equivalence as program segments is stronger than the corresponding equiv-
alence (by taking Q = 0). In some cases, the two concepts are the same. For
example ...