On the contribution of backward jumps to instruction sequence expressiveness

Jan A. Bergstra, Inge Bethke

We investigate the expressiveness of backward jumps in a framework of formalized sequential programming called program algebra. We show that - if expressiveness is measured in terms of the computability of partial Boolean functions - then backward jumps are superfluous. If we, however, want to prevent explosion of the length of programs, then backward jumps are essential.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment