On the Power of Arrays In Universal Languages

Abstract

A language with arrays but with no conditional statement is shown to be universal under "simulation", a relation on programs frequently encountered in the practical computing world. Any r.e. set can be enumerated by a program (in this language) whose flow chart is a single loop which contains no alternate execution paths normally thought necessary for computation in general. A related result is shown for any general program, thus characterizing selection in arrays as at least as powerful as conditional branching in programs. These results are related to important results in schemata.