Equivalences on program schemes

摘要

A program scheme may be informally described as a program with the interpretation (i.e., the meaning of the basic instructions or standard functions) left unspecified. This paper studies the equivalence of program schemes under different classes of interpretations, with emphasis on those in which the functions are permitted to be partial. Several different equivalence relations are defined, and their interrelationship and solvability examined both for the class of all program schemes, and for each subclass (n≥1) in which the number of registers is at most n.