FOM: Natural examples

[Stephen Fenner]

On Tue, 12 Oct 1999, Joe Shipman wrote:

> > BTW, the solution of Post's problem presented first in Soare's book is the
> > construction of a noncomputable low c.e. set, and is simpler than the F-M
> > construction.
> 
> I don't have this book -- can you sketch this proof for us?

Glad to.

First, one might question what FOM content this has, but if this helps
someone to isolate any special "natural" properties of the set
constructed, then that would shed light on the on-going discussion of
natural intermediate c.e. sets.  I'll use more detail than a sketch, for
the sake of those not so familiar with these proofs.

Notation:

lowercase vars range over the natural numbers, uppercase vars range over
subsets (equivalently, unary predicates) of the natural numbers.

{e}^A(x)  -  the e'th oracle TM running with oracle A on input x
phi_e     -  the e'th computable partial function (computed by the e'th
             TM)
W_e       -  the e'th c.e. set = domain(phi_e)
             (a set is c.e. iff it equals W_e for some e)
W_{e,s}   -  the set of numbers x <= s such that phi_e(x) halts within s
             steps ( clearly, W_e = union_s W_{e,s} )
A'        -  the Turing jump of A = { e | {e}^A(e) halts }
comp(A)   -  the set-theoretic complement of A (in the natural numbers)
use({e}^A(x),s)
          -  this is the least upper bound on all oracle queries made by
             {e}^A(x) during its first s steps

Actually, Soare constructs a low simple set.  This construction is adapted
from Soare, Recursively Enumerable Sets and Degrees, Springer Omega
Series, 1987, pp. 111-112.

A is _low_ if A' = emptyset'
A is _simple_ if A is c.e. and coinfinite, but comp(A) contains no
infinite c.e. subset.  It's easy to see that simplicity implies
noncomputability.

By the Limit Lemma, a set A is low iff A' is computably approximable, that
is, there is a computable f(x,s) such that for all x,

    lim_{s goes to infinity} f(x,s) exists and = A(x)

To construct a low simple set A, there are two types of requirements:

Positive requirements that put elements into A to make it simple;
Negative requirements that "freeze" A so that A' can be computably
approximated.

We define finite sets A_0 subset A_1 subset A_2 subset ... in stages, and
we let A be the union of all the A_i.  Here are the two kinds 
of requirements:

P_e :  if W_e is infinite, then W_e intersect A =/= emptyset.

N_e :  if [ for infinitely many s, {e}^{A_s}(e) halts within s steps ]
       then {e}^A(e) halts.

If all the P_e are met, then A will be simple (the construction will
guarantee that A is coinfinite).  If all the N_e are (eventually) met,
then it's not hard to see that A' is approximated by the computable
function

                    / 1    if {e}^{A_s}(e) halts within s steps
          f(x,s) = <
                    \ 0    otherwise


BEGIN CONSTRUCTION
Stage 0 : Let A_0 = emptyset.

Stage s+1 : We're given A_s.  Choose the least i <= s such that

(1)   W_{i,s} intersect A_s = emptyset, and

(2)   (exists x > 2i) [ x in W_{i,s}  and
                        (forall e <= i)[ use({e}^{A_s}(e),s) < x ] ]

If i exists, choose the least x satisfying (2).  Put x into A_{s+1} (that
is, A_{s+1} := A_s union {x}), and say that P_i "receives attention."
Note that P_i is now satisfied once and for all.  If i doesn't exist, then
do nothing (A_{s+1} := A_s).
END CONSTRUCTION

I'll only sketch why this construction works.  The whole construction
is effective, so A is c.e.  The priorities of the
requirements are (from highest) N_0, P_0, N_1, P_1, ....  At stage s, each
N_e (for e<=s) builds a "wall" over A of length use({e}^{A_s}(e),s),
preventing elements up to this value from entering A.  The wall can be
punctured (injuring N_e) only when a higher-priority P_i receives
attention.  The positive requirements are never injured, so each N_e is
injured at most e times.  After N_e is injured for the last time, its wall
stays up, freezing the computation {e}^A(e).  Hence A is low.

If any W_i is infinite and threatens to have empty intersection with A,
then P_i will eventually receive attention, since it is only hampered by
walls set up by finitely many higher-priority N_e.  Thus, all the P_e are
satisfied.

Finally, the lower of 2i on x in condition (2) guarantees that
A intersect {0,1,...,2i} has at most i elements, for all i (remember, P_i
receives attention at most once).  Thus A is coinfinite and thus simple.
QED