Diagonalization, uniformity, and fixed-point theorems (Q1201287): Difference between revisions

New fixed-point theorems for subrecursive classes are derived, together with a widely applicable theorem on the uniformity of certain reductions. The present formulation extends the main theorem of \textit{U. Schöning} ``A uniform approach to obtain diagonal sets for complexity classes'' [Theor. Comput. Sci. 18, 95-103 (1982; Zbl 0485.68039)] to cases which involve infinitely many diagonal classes, and which allow each diagonal class to contain uncountably many members. The other theorem is similar to the ``uniform boundedness theorem'' of classical analysis, and extends work of J. Grollmann and A. Selman.