Abstract families of processors

摘要

A processor is a nondeterministic Turing-like automaton with auxiliary storage. An abstract family of processors (AFP) consists of all processors that use the storage in the same way. For a family of operations to be the output functions of an AFP, it is necessary and sufficient that it include all homomorphisms and their inverses and be closed under functional union, composition, iteration and cartesian product; necessary and sufficient that its domains (ranges) form a full AFL closed under ∩ and iterated homomorphism and that its argument-value relations be all those representable by sets of this AFL. For a family of word-sets to be the accepted languages of an AFP, it is necessary and sufficient that it be a full AFL closed under ∩ and iterated homomorphism.