{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T04:03:04Z","timestamp":1648958584218},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1970,10]]},"abstract":"\n 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\n L<\/jats:italic>\n 2<\/jats:sub>\n of loop programs defining the class of elementary functions. A solution is given for the class\n L<\/jats:italic>\n 1<\/jats:sub>\n 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\n L<\/jats:italic>\n 2<\/jats:sub>\n ; but as before, a solution is given for the class\n L<\/jats:italic>\n 1<\/jats:sub>\n . It is concluded, therefore, that there is a barrier of unsolvability between the classes\n L<\/jats:italic>\n 1<\/jats:sub>\n and\n L<\/jats:italic>\n 2<\/jats:sub>\n .\n <\/jats:p>","DOI":"10.1145\/321607.321621","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:26:10Z","timestamp":1027769170000},"page":"729-738","source":"Crossref","is-referenced-by-count":34,"title":["The Equivalence Problem of Simple Programs"],"prefix":"10.1145","volume":"17","author":[{"given":"D.","family":"Tsichritzis","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Toronto, Toronto, Ont., Canada. and Princeton University, Princeton, New Jersey"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_2","first-page":"112","volume":"10","author":"Iteration","year":"1963","journal-title":"Amer. Math. Sac."},{"key":"e_1_2_1_2_2","first-page":"757","volume":"5","author":"Analysis","journal-title":"IEEE Trans. EC-15"},{"key":"e_1_2_1_3_2","volume-title":"Proc. Congress on Logic, Methodology and Philosophy of Science","author":"Ai","year":"1964"},{"key":"e_1_2_1_4_2","volume-title":"McGraw-Hill","author":"Avis M.","year":"1958"},{"key":"e_1_2_1_5_2","unstructured":"GRZEGORCZrK A. Some classes of recursive functions. Rozprawy Matematycznc (Warsaw poland) 4 (1953) 1-46. GRZEGORCZrK A. Some classes of recursive functions. Rozprawy Matematycznc (Warsaw poland) 4 (1953) 1-46."},{"key":"e_1_2_1_6_2","unstructured":"GUARD J. Lecture notes on recursive functions and mathematical machines. Princeton U. Princeton N. J. 1967. GUARD J. Lecture notes on recursive functions and mathematical machines. Princeton U. Princeton N. J. 1967."},{"key":"e_1_2_1_7_2","unstructured":"KLEENE S.C. Introduction to MetamathenmHcs. Van Nostrand Princeton N. J. 1952. KLEENE S.C. Introduction to MetamathenmHcs. Van Nostrand Princeton N. J. 1952."},{"key":"e_1_2_1_8_2","unstructured":"MEYER A. R. Depth of nesting of primitive recursion. Manuscript obtained through private correspondence. MEYER A. R. Depth of nesting of primitive recursion. Manuscript obtained through private correspondence."},{"key":"e_1_2_1_9_2","first-page":"465","volume-title":"Proc. 22nd Nat.Conf. ACM","year":"1967"},{"key":"e_1_2_1_10_2","volume-title":"IBM Res: Rep. RC 1817","year":"1967"},{"key":"e_1_2_1_11_2","first-page":"17","volume-title":"Proc. First Hawaii International Conference on Information Sciences and Systems, U. of Hawaii","year":"1968"},{"key":"e_1_2_1_12_2","unstructured":"MINSKY M' Computation Finite and Infinite Machines. Prentice-Hall Englewoud Cliffs N. J . 1967 MINSKY M' Computation Finite and Infinite Machines. Prentice-Hall Englewoud Cliffs N. J . 1967"},{"key":"e_1_2_1_13_2","unstructured":"PETER R. Recursive Functions. Academic Press New York 1967. PETER R. Recursive Functions. Academic Press New York 1967."},{"key":"e_1_2_1_14_2","first-page":"3","volume":"15","author":"Cm E","year":"1965","journal-title":"Math."},{"key":"e_1_2_1_15_2","first-page":"703","volume-title":"SecondHawaii International Conference on Information Sciences and Systems, U. of Hawaiil :HoZnolulu","author":"Zm D.","year":"1969"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/321607.321621","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T19:30:11Z","timestamp":1614713411000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/321607.321621"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1970,10]]},"references-count":15,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1970,10]]}},"alternative-id":["10.1145\/321607.321621"],"URL":"http:\/\/dx.doi.org\/10.1145\/321607.321621","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1970,10]]}}}