The Equivalence Problem of Simple Programs
D. Tsichritzis · Journal of the ACM · 1970
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 .