About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
STOC 1972
Conference paper
Characterizations of flowchartable recursions short version
Abstract
In this paper we give new characterizations for the flowchartability of recursive functionals. The general question of flowchartability is recursively undecidable. We present here an effective map from recursions to 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 of flowcharting, depending only on recursion structure, such that a recursion is flowchartable by this method if and only if its representative is flowchartable. The main results of the paper are (1) that such 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.