On the Power of Arrays In Universal Languages
Permanent Link(s)
Collections
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-01
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR73-155
Type
technical report