DECOMPOSITION OF GÖDEL NUMBERINGS INTO MINIMAL NUMBERINGS

Abstract This article studies the question of which classes of numberings can be generated by the direct sums of computable uniformly minimal sequences of numberings (in particular, Friedberg and positive numberings). For the class of Friedberg numberings, this question was initiated by Britta Schinzel in her 1982 paper. In this article, we show that the class of Gödel numberings is generated by the direct sums of computable uniformly positive sequences of universal numberings and that there exists a conull class of oracles computing sequences of Friedberg numberings with programmable direct sums. We further show that all computable numberings of a fairly wide class of families of total recursive functions (containing, for example, the family of all primitive recursion functions) are generated by the direct sums of computable sequences of their incomparable Friedberg numberings. On the other hand we prove that no family of partial recursive functions has a computable sequence of Friedberg numberings whose direct sum is acceptable.