Even Simple Programs Are Hard To Analyze
- 1 April 1977
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 24 (2) , 338-350
- https://doi.org/10.1145/322003.322016
Abstract
A simple programming language which corresponds in computational power to the class of generalized sequential machines with final states is defined. It is shown that a variety of questions of practical programming interest about the language are of nondeterministic linear space complexity. Extensions to the language are defined (adding arithmetic and array data structures) and their complexity properties are explored. It is concluded that questions about halting, equivalence, optimization, and so on are intractable even for very simple programming languages.Keywords
This publication has 2 references indexed in Scilit:
- Proving containment of bounded AFLJournal of Computer and System Sciences, 1975
- The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machinesJournal of the ACM, 1968