Hierarchies of recursive computations†

†This research was supported in part by NSF grant MCS 74-02338.

Abstract

A recursive version of the Turing machine model is used to analyze the time and storage complexity of recursive algorithms. Hierarchy theorems are proven for time and for width of recursion (the amount of storage used at a level). A particular language is shown to be the “hardest” language to recognize without recursion. Previous results relating recursive and non-recursive time bounded computations are sharpened.

Keywords:

• Turing machine
• Tape complexity
• Time complexity
• Recursive algorithms
• Nondeterministic algorithm
• Hierarchy

C.R. Categories:

• 5.25
• 5.26
• 5.23

†This research was supported in part by NSF grant MCS 74-02338.

†This research was supported in part by NSF grant MCS 74-02338.

Notes

†This research was supported in part by NSF grant MCS 74-02338.