The Equivalence Problem of Simple Programs

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 L2 of loop programs defining the class of elementary functions. A solution is given for the class L1 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 L2; but as before, a solution is given for the class L1. It is concluded, therefore, that there is a barrier of unsolvability between the classes L1 and L2.

REFERENCES

• 1: AXT, P. Iteration of primitive recursion, Abstract 597-182. Notices Amer. Math. Sac. 10, No. lPt. 1 (Jan. 1963), 112.
• 2: BERNSTEIN, A. J. Analysis of programs for parallel processing. IEEE Trans. EC-15, 5 (Oct' 1966), 757-763.
• 3: COBHAM Ai The intrinsic computational difficulty of functions, Proc. Congress on Logic, Methodology and Philosophy of Science, Haifa, Israel, 1964 (North-Holland, Amsterdam, 1964),, pp: 24-30.
• 4: DAvis, M. Computability and Unsolvability. McGraw-Hill, New York, 1958.
• 5: GRZEGORCZrK, A. Some classes of recursive functions. Rozprawy Matematycznc (Warsaw, poland) 4 (1953), 1-46.
• 6: GUARD, J. Lecture notes on recursive functions and mathematical machines. Princeton U., Princeton, N. J., 1967.
• 7: KLEENE, S.C. Introduction to MetamathenmHcs. Van Nostrand, Princeton, N. J., 1952.
• 8: MEYER, A. R. Depth of nesting of primitive recursion. Manuscript obtained through private correspondence.
• 9: Albert R. Meyer , Dennis M. Ritchie, The complexity of loop programs, Proceedings of the 1967 22nd national conference, p.465-469, January 1967, Washington, D.C., United States [doi>10.1145/800196.806014]
• 10: . AND --. Computational complexity and program structure. IBM Res: Rep. RC 1817, May 15, 1967.
• 11: AND ..... A classification of functions by computational complexity. Proc. First Hawaii International Conference on Information Sciences and Systems, U. of Hawaii, Honolulu, Hawaii, 1968, pp. 17-19.
• 12: Marvin Lee Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Upper Saddle River, NJ, 1967
• 13: PETER, R. Recursive Functions. Academic Press, New York, 1967.
• 14: RITCmE, R. Classes of primitive recursive functions based on Ackermann's function. Pacific J, Math. 15, 3 (1965), 1027-1037.
• 15: TSCHRITZm, D. Some unsolvable problems and partial solutions. Tech. Rep: NO. 69, Dep. of Elec. Eng.; Princeton Uii Princeton, N, J. (Summary in Proc. SecondHawaii International Conference on Information Sciences and Systems, U. of Hawaiil :HoZnolulu, Hawaii, 1969, pp. 703-706.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Theory, Verification