Diagonally non-computable (DNC) functions and immune sets are classical
recursion theory concepts that also appear frequently in Kolmogorov
complexity and algorithmic randomness. Previous work has shown that the
immune and effectively immune sets are bothn complexity lower bounds for
incomparable notions of randomness such as Kurtz randomness and DNC
functions. In 2012, Carl Jockusch and Andrew Lewis-Pye proved that every
DNC function computes a bi-immune set. Since every Kurtz random set also
computes a bi-immune set, this showed that the bi-immune sets also form a
lower bound for the Kurtz random sets and the DNC functions. They asked
whether every DNC function computes an effectively bi-immune set. We
construct a DNC function that computes no effectively bi-immune set,
thereby answering their question in the negative.
Thinking about UNT?
It's easy to apply online. Join us and discover why we're the choice of over 46,000 students.
Apply now