Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Subrecursive Program Schemata I and III. Undecidable Equivalence Problems and II. Decidable EquivalenceProblems

Subrecursive Program Schemata I and III. Undecidable Equivalence Problems and II. Decidable EquivalenceProblems

File(s)
72-124.ps (1.27 MB)
72-124.pdf (4.79 MB)
Permanent Link(s)
https://hdl.handle.net/1813/5980
Collections
Computer Science Technical Reports
Author
Constable, Robert L.
Muchnick, S.S.
Abstract

The study of program schemata and the study of subrecursive programming languages are both concerned with limiting program structure in order to permit a more complete analysis of algorithms while retaining sufficiently rich computing power to allow interesting algorithms. In this paper we combine these approaches by defining classes of subrecursive program schemata and investigating their equivalence problems. Since the languages are all subrecursive, any scheme written in any one of them must halt (as long as we assume the basic functions and predicates are all total). Hence equivalence of schemes is the first question of interest we can ask about these languages. We consider schematic versions of various subrecursive programming languages similar to the Loop language. We distinguish between Pre-Loop and Post-Loop languages on the basis of whether the exit condition in an iteration loop is tested before iteration, as in Algol (Pre-), or after iteration, as in FORTRAN (Post-). We show that at the program level all these languages have the same computing power (the primitive recursive functions) and all have unsolvable equivalence problems (of arithmetic degree $\Pi^{0}{1}$). But at the level of schemes, Pre-Loop has an unsolvable equivalence problem, while at least one formulation of Post-Loop has a solvable equivalence problem. If L is a programming language or scheme language, then we denote by E(L) the equivalence problem in L. The basic languages considered are: Loop ($\equiv$ Pre-Loop) - Loop language for primitive recursive functions. Post-Loop - Post-Loop language for primitive recursive functions. Loop${\Diamond}$ - Loop language with restricted conditionals. L [D, ()] - Loop schemata over D with identity. L${\Diamond}$ [D, ()] - Loop schemata with conditionals. PL [D, ()] - Post-Loop schemata over D. PL${\Diamond}$ [D, ()] - Post-Loop schemata with conditionals. P - Program (flowchart) schemata. P${d}$ - Program schemata with DO-statements. In contrast to (pure) Loop schemata studied previously by the first author, some of these languages contain the identity function so that a pure data transfer, $X \leftarrow Y$, is possible. Moreover, the equivalence algorithms given here are for the special case of linear schemes (to be defined below) with monadic function variables. Linear schemes are designated by placing L before the name of the more general class, thus LL for linear Loop, LPL for linear Post-Loop, etc. In all schemes considered here the functions are monadic, so no special designation of function rank is provided. It is well known that E(P) is recursively unsolvable and E(P) $\in \Pi^{0}{2}$. We show that E(Loop), E(Post-Loop), E(L$_{\Diamond}$) (both with and without the pure data transfer), and E(L) are recursively unsolvable, while E(LPL) is recursively solvable. The extension of the equivalence algorithm for LPL to polyadic functions appears at present to be a tedious but straightforward modification to the monadic algorithm. We are hopeful that a simpler and more generally applicable technique will emerge for demonstrating solvability or unsolvability of this class of equivalence problems. The algorithm and proofs given here are but a crude first step in delimiting this problem.

Date Issued
1972-03
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR72-124
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance