Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. On the Power of Arrays In Universal Languages

On the Power of Arrays In Universal Languages

File(s)
73-155.ps (387.82 KB)
73-155.pdf (1.59 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6006
Collections
Computer Science Technical Reports
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
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

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance