On transformations of programs

摘要

A treatment is given of a class of program transformations Σ with the property that for each program P, both P and Σ(P) compute the same function. Many transformations encountered in the theory of computation can be shown to be in the class and, hence, formally proved to preserve equivalence. As an example, the theory is applied to the proof of a speed up theorem in computational complexity.