GERALD E. SACKS
In MemoriamProfessor Joseph R. Shoenfield
Abstract An informal sketch (with intermittent details) of parts of E-Recursion theory, mostly old, some new, that stresses intuition. The lack of effective unbounded search is balanced by the availability of divergence witnesses. A set is E-closed iff it is transitive and closed under the application of partial E-recursive functions. Some finite injury, forcing, and model theoretic constructions can be adapted to E-closed sets that are not Σ1 admissible. Reflection plays a central role.
§1. Initial Intuitions. One of the central intuitions of classical recursion theory is the effectiveness of unbounded search. Let A be a nonempty recursively enumerable set of nonnegative ...