Depth-bounded computation

摘要

A programming language designed for studies of parallelism and based on Wagner'suniformly reflexive structures is introduced. The measure of depth of computation in the language is studied. The partial recursive functions are shown to be computable in uniformly bounded depth. A comparison of the measure with other proposed measures of computational complexity leads to the suggestion of a list of properties to be checked in classifying such measures.