The Equivalence Problem of Simple Programs
Author:
Open Access
- 1 October 1970
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 17 (4) , 729-738
Abstract
Many problems, some of them quite meaningful, have been proved to be recursively unsolvable for programs in general. The paper is directed toward a class of programs where many decision problems are solvable. The equivalence problem has been proved to be unsolvable for the class L 2 of loop programs defining the class of elementary functions. A solution is given for the class L 1 defining the class of simple functions. Further, a set of other decision problems not directly connected with the equivalence problem is investigated. These problems are found again to be unsolvable for the class L 2 ; but as before, a solution is given for the class L 1 . It is concluded, therefore, that there is a barrier of unsolvability between the classes L 1 and L 2 .Keywords
This publication has 2 references indexed in Scilit:
- The complexity of loop programs1967
- Analysis of Programs for Parallel ProcessingIEEE Transactions on Electronic Computers, 1966