degrees of unsolvability

[Stephen G. Simpson]

The American Mathematical Society Joint Mathematics Meetings will be in
Boston, January 4-7, 2023.  It will include an AMS Special Session in honor
of Gerald E. Sacks.  Here is an abstract of my 45-minute invited talk for
that session.

Degrees of Unsolvability

Stephen G. Simpson
Vanderbilt University
Pennsylvania State University
personal.psu.edu/t20
sgslogic at gmail.com
September 6, 2022

Studying degrees of unsolvability in the late 1960s with Hartley
Rogers Jr. and Gerald E. Sacks, I noticed that other than 0 and 0'
there are no specific, natural examples of recursively enumerable
Turing degrees.  And although there are many examples of specific,
natural Turing degrees, all of them are of the form 0^(alpha) where
alpha = some specific, natural, ordinal number, e.g., alpha = omega.
I asked Gerald about this, but his answers did not satisfy me.  And
subsequent to Gerald's book *Degrees of Unsolvability* there were three
other books with the same title, but none of them answered my
question.  Now I am writing a fifth book with the same title, but my
book has a different emphasis.  Namely, in addition to the
0^(alpha)'s, I present many other specific, natural examples of
degrees of unsolvability.  To be sure, my examples do not belong to
the semilattice D_T of Turing degrees.  However, they belong to the
*Birkhoff completion* of D_T, denoted widehat D_T.  And many of them
belong to a certain countable sublattice of widehat D_T which is
analogous to the recursively enumerable Turing degrees.  Among these
examples are the degrees of the following unsolvable problems: to
compute at least one real which is *random *in the sense of Martin-L"of;
to compute at least one real which is half-random; to compute at least
one real which is a-random, where a = some fixed specific, natural,
rational number in the interval 0<a<1; to compute at least one real
whose effective Hausdorff dimension is 1; to compute at least one real
which is f-random, where f is some fixed specific, natural function
such as f(n) = sqrt n or f(n) = log_2 n or f(n) = n - 2 log_2 n; to
compute at least one real which is *complex* in the sense of
Kjos-Hanssen/Merkle/Stephan; to compute at least one function which is
diagonally non-recursive; to compute at least one function which is
diagonally non-recursive and recursively bounded; to compute at least
one real which is shift-complex; to compute at least one real x such
that 0^(alpha) is LR-reducible to x, where alpha = some fixed
specific, natural ordinal number.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20220906/e825f446/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: abstract-220906.pdf
Type: application/pdf
Size: 36745 bytes
Desc: not available
URL: </pipermail/fom/attachments/20220906/e825f446/attachment-0001.pdf>