JavaScript is disabled for your browser. Some features of this site may not work without it.
On the Power of Arrays In Universal Languages

Author
Johnson, Donald B.
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.
Date Issued
1973-01Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR73-155
Type
technical report