Confusion about definitions of a universal function

Question

I've seen these two definitions of a universal partial function for partial computable functions of one variable:

• It is a (partial computable, I suppose, though it does not appear in the source) function $U:N\times N\to N$ such that for all computable partial functions $f:N\to N$ there is a program $p\in N$ such that for all $x\in N$ one has $f(x)=U(p,x)$.

• It is a partial computable function $U:N\times N\to N$ such that for all $x,y\in N$, one has $U(x,y)=\phi_x(y)$ if $\phi_x(y)$ is defined and $U(x,y)$ is undefined if $\phi_x(y)$ is undefined.

The first definition is from a classroom, the second is from Rogers' book (but he calls the function $U$ by the name $\phi_z$.) First, just to make sure, is the first definition precise? And secondly, are they equivalent? If so, why? The first definition involves existential and universal quantifiers whereas the second only involves universal quantifiers.

Moreover, I found this version:

• 

This definition resembels the first one. It says that for every computable $f$ there is $n$ such that for all $x$ we have $U(n,x)=f(x)$. But $U$ is not required to be computable, only $U(n,-)$ is required to be computable. Is this equivalent to requiring that $U$ be computable?

Update: probably the third definition is weaker. The source says "Obviously, a universal function exists for any countable class (and only for these classes)" (by the way, why? It's not obvious to me) and then states the theorem "There exists a computable function of two variables universal for the class of computable functions of one variable." The theorem is (I believe) about the existence of the function from the first definition, right?

Answer 1

The two definitions are not equivalent. But in my opinion, neither of the is good: the first is just insufficient for developing a good computability theory, while the latter rests on an odd circumlocution which I think just confuses matterss.

Before diving into the issue, let me make a couple points:

• All functions are partial.

• According to all the approaches, we're presupposing that we've already defined what it means to be a partial computable $n$-ary function for all $n$ - or at least for $n=1,2$.

• I'm going to avoid using the term "program" since it's dangerously loaded.

---

Let's start with Rogers' approach, your second definition. In my opinion his approach here (if it's being accurately quoted - I don't have Rogers' book on-hand) is rather silly.

Specifically, by the time he introduces universality Rogers has already chosen a sequence $$\mathfrak{S}=(\phi_e)_{e\in\mathbb{N}}$$ which enumerates (with repetition) the partial computable functions. This sequence has a naturally associated binary function $$U_\mathfrak{S}: (a,b)\mapsto \phi_a(b).$$

Clearly $U_\mathfrak{S}$ is the only possible universal function according to Rogers' definition, so if Rogers' claims "There is a universal function" what he really means is "the specific function $U_\mathfrak{S}$ is computable."

(Actually it's even worse: set-theoretically, $\mathfrak{S}$ literally is $U_\mathfrak{S}$ since a sequence of elements of $X$ is just a map $\mathbb{N}\rightarrow X$. This all seems very silly to me, so I'm a little suspicious that there might be a transcription error here.)

---

OK, now let's look at the first definition.

This is much more flexible. In particular, according to this definition universal functions need not be unique. Looking at Asaf Karagila's example, let $U_\mathfrak{S}$ be the unique Rogers-universal function above, and consider the function $\hat{U}:\mathbb{N}^2\rightarrow\mathbb{N}$ given by $\hat{U}(2k, i)\downarrow =0$ and $\hat{U}(2k+1, i)\simeq U_\mathfrak{S}(k,i)$ for all $k,i\in\mathbb{N}$. Then:

• $\hat{U}$ is not Rogers-universal (since $\hat{U}\not=U_\mathfrak{S}$.

• $\hat{U}$ is however universal in the sense of the first definition.

Indeed, if you ask someone to define "Turing complete" they'll probably give you a version of the first definition. But they shouldn't, because ...

---

... the right notion of universality to consider is actually the following:

$F:\mathbb{N}^2\rightarrow\mathbb{N}$ is an acceptable numbering iff:

• $\{F(x,-):x\in\mathbb{N}\}$ is just the set of computable functions,

• $F$ itself is computable, and

• For every binary computable function $G:\mathbb{N}^2\rightarrow\mathbb{N}$ there is a total computable $g$ such that $$G(a,b)\simeq F(g(a),b)$$ for all $a,b\in\mathbb{N}$.

Those first two bulletpoints amount to your first definition, and the third is the new bit. (Note that the second and third bulletpoints imply the first bulletpoint, but meh.) It has various equivalent rephrasings; I've picked the one I think is clearest.

Both the definitions you give have issues with acceptability:

• The first definition simply doesn't imply acceptability. In particular, there are universal functions in its sense which yield terrible computability theories - e.g. Friedberg numberings, for which Rice's theorem and the Recursion theorem each fail.

• In the second definition, the unique Rogers-universal function $U_\mathfrak{S}$ will turn out to be acceptable - because of Rogers' specific choice of $\mathfrak{S}$. But if Rogers had picked a different enumeration of the computable functions, the resulting Rogers-universal function might not have been acceptable (in which case Rogers would have been sad).

So the first definition is just bad, and the second definition is weirdly redundant.