Skip to main content
2 of 2
Clarified totality, suggested by Joel's comment
Eric Astor
  • 256
  • 1
  • 10

Is DNC/DNR stronger than "prompt" non-computability?

We propose a (probably not new) definition. Let $\varphi_e$ be an effective enumeration of the partial computable functions.

A total function $f$ is promptly non-computable (PNC) [or promptly non-recursive, PNR] if there exists a computable function $h$ such that, for all $\varphi_e$, there is some $m\le h(e)$ with $\varphi_e(m)\ne f(m)$. (Possibly because $\varphi_e(m)$ diverges.) In other words, $f$ differs from $\varphi_e$ by position $h(e)$.

This is a weakening of diagonal non-computability (DNC) [or diagonally non-recursive, DNR], where we say $f$ is DNC if, for all $\varphi_e$, $\varphi_e(e)\ne f(e)$. Naturally, DNC would be a special case of PNC, taking $h$ to be the identity.

Does every PNC function compute a DNC function? Or is DNC actually stronger than PNC?

Eric Astor
  • 256
  • 1
  • 10