Diagonalization, uniformity, and fixed-point theorems

We derive new fixed-point theorems for subrecursive classes, together with a theorem on the uniformity of certain reductions, from a general formulation of the technique of delayed diagonalization. This formulation extends the main theorem of U. Schöning (Theoret. Comput. Sci. 18 (1982), 95–103) to cases which involve infinitely many diagonal classes C k, and which allow each C k to contain uncountably many members. The main technical work ties the familiar concept of a witness function directly to the often-studied Cantor-set topology on languages, and provides a “delay construction” which refines those due to Schöning, S. Breidtbart, and D. Schmidt. Our “a. e. ” fixed-point theorems do not require that the “programming system” for the subrecursive class in question be well-behaved; we compare them to results which do. The other theorem is similar to the “uniform boundedness theorem” of classical analysis, and extends work of J. Grollmann and A. Selman.

Authors

• Kenneth W. Regan

Keywords

No keywords are indexed for this paper.