Characterizations of flowchartable recursions

摘要

In this paper we give new characterizations for the flowchartability of recursive functionals. Here flowchart means flowchart with counters (or any arbitrary control structure) and nonflowchartability essentially means requiring access to an unbounded number of data locations during computation of the functional. The general question of flowchartability is recursively undecidable. We present here an effective map from the class of all recursions to a subclass of “representatives” for which the question is decidable. The decision provides a good approximation to a characterization for general flowchartability in the following senses: (1) if a representative is flowchartable, then the recursions it represents are, and (2) there is a straightforward method for flowcharting arbitrary recursions, depending only on recursion structure, such that a recursion is flowchartable by this method if, and only if, its representative is flow-chartable.The main results of the paper are (1) that a representative is flowchartable if, and only if, it is simple or linear, and (2) that, when the context is restricted so that only invertible operations are considered, such a representative is flowchartable if, and only if, it is nested. The terms “simple” and “linear” have been defined in previous papers in the area, although they are extended slightly in this one. The term “nested” is introduced here. Simple, linear, and nested recursions are very easy to identify by inspection.