4
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Could you clarify: you insist that $f$ is a total function? $\endgroup$
    – Joel David Hamkins
    Commented Sep 23, 2015 at 17:40
  • $\begingroup$ @JoelDavidHamkins Yes, for the same reason we do so for standard DNC functions; if we allow partial functions to be DNC, there's a trivial computable example. (Specifically, U(e) + 1). $\endgroup$
    – Eric Astor
    Commented Sep 23, 2015 at 17:51
  • $\begingroup$ Well, that function wouldn't have $U(e)\neq f(e)$ in the case $U(e)\uparrow$, since both sides would diverge equally, so I don't take it as a "counterexample". I think the concept makes fine sense when $f$ is partial, provided that you really have $\varphi_e(m)\neq f(m)$, either because one side diverges and the other doesn't, or both converge, but to different values. But it is also fine to require that $f$ is total. $\endgroup$
    – Joel David Hamkins
    Commented Sep 23, 2015 at 17:54
  • $\begingroup$ Ah. Good point, and that's part of why we restrict to total functions... to avoid the debate of whether if $U(e)\uparrow$ and $f(e)\uparrow$, we can say that $U(e)=f(e)$. Thanks for making me clarify. $\endgroup$
    – Eric Astor
    Commented Sep 23, 2015 at 17:57

1 Answer 1

Reset to default
7
$\begingroup$

The graph of the course-of-values variant $$\{(x,(f(0),\dots,f(x))): x\in \mathbb N\}$$ of such a function would be effectively immune. Namely, if we enumerate a subset of this graph then there is an associated partial recursive function. Therefore it is equivalent to DNR.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I see - thanks! I do wonder if there's a nice direct construction, though, taking us from "PNC" to DNR. $\endgroup$
    – Eric Astor
    Commented Sep 24, 2015 at 6:14
  • $\begingroup$ @EricAstor I guess if you trace through the proof that effectively immune computes DNR, the DNR function $g$ ends up being something like $g(x)=\langle f(0),\dots,f(h(x))\rangle$ for a certain $h$. So maybe one can get that a computably bounded $\mathsf{PNC}$ function computes a computably bounded $\mathsf{DNC}$ function, and study the computable growth rates. $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Sep 24, 2015 at 7:03
  • $\begingroup$ Huh. I can't seem to get my hands on a copy of that proof, actually... and I'm not sure I've seen it cited before. Can you suggest a text or paper? $\endgroup$
    – Eric Astor
    Commented Sep 24, 2015 at 18:09
  • $\begingroup$ If memory serves it is in Jockusch's 1989 paper on DNR functions. $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Sep 24, 2015 at 18:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .