Necessary and sufficient conditions for the universality of programming formalisms (Q801666)

Over many familiar datatypes the notion of ''computable'' coincides with the notion of ''flowchartable''. For example, any partial recursive function is defined by a flowchart program over the datatype \((\omega,=,succ,0)\) where succ is the successor operation on the set \(\omega\) of natural numbers. It is also known that flowcharts are not a universal programming formalism over arbitrary datatypes, in the sense that the notion of ''computable'' is strictly more general than the notion of ''flowchartable''. In this paper we consider various extensions and restrictions of the basic formalism of flowcharts, and then for every such formalism, we characterize the datatypes over which the computable functions are exactly the functions programmable in this formalism. We say that a function is computable over a datatype if it is effective relative to the primitive operations and relations of the datatype (which are assumed to be defined everywhere on the domain of the datatype). Our results are expressed algebraically, putting simple restrictions on the primitive operations and relations of datatypes. For example, we prove that the notion of ''computable'' over an arbitrary (one-sorted) datatype A coincides with the notion of ''definable by a flowchart program over A with recursive calls'' if and only if: (\(\forall k)(\exists \ell)\) (\(\forall\) k-tuple a of elements in the domain of A) [If a generates more than \(\ell\) elements then a generates infinitely many elements]. We also prove that the notion of ''computable'' over an arbitrary datatype A coincides with the notion of ''definable by a flowchart program over A with counters'' if and only if: (\(\forall k)(\exists \ell)\) (\(\forall\) k- tuple a of elements in the domain of A) [Every element at all generated by a can be generated using \(\ell\) memory locations]. We prove several other similar results. In the last section of the paper, we examine programmability over familiar algebraic structures (groups, rings, and fields).