Characterization of computationally universal functions Is it correct to state that $u$ is a universal function if and only if
$$
\forall f : \text{RE} \quad
\exists g : \text{R} \quad
\exists h : \text{R} \quad
f = h \circ u \circ g
$$
where RE is the set of recursively enumerable functions and R is the set of recursive functions? (Should R be replaced with something like PR?) If so, does anyone know of a reference that states universality in this generic form?
Defining &quot;universal function&quot;
I suppose we could define &quot;universal function&quot; itself as follows: Let $\phi : \mathbb{N} \rightarrow \mathbb{N} \rightharpoonup \mathbb{N}$ be an enumeration of all partial computable functions $\mathbb{N} \rightharpoonup \mathbb{N}$. Let $\psi : \mathbb{N} \rightharpoonup \mathbb{N}$ where
$$
\psi(n) = \phi(\pi_1(n))(\pi_2(n))
$$
where $\pi_1, \pi_2 : \mathbb{N} \rightarrow \mathbb{N}$ are the first and second Cantor unpairing functions. Then $u : A \rightarrow B$ is universal if and only if
$$
\exists g : R \cap (\mathbb{N} \rightarrow A) \quad
\exists h : R \cap (B \rightarrow \mathbb{N}) \quad
\psi = h \circ u \circ g
$$
This resembles a definition of computable functions given in page 24 of Cutland's Computability: An Introduction to Recursive Function Theory.
Addendum
In a sense, I'm looking for a definition of universality that is more &quot;axiomatic&quot;, &quot;abstract&quot;, and &quot;generic&quot; than the definition that is usually given, which pertains to partial functions from naturals to naturals specifically. My candidate definition requires only that RE be defined/understood over the relevant domain. (From that, co-RE and therefore R fall out automatically.)
To give an example of what I mean from a different area of mathematics, the reals can be constructed as Cauchy sequences or Dedekind cuts of rationals. However, they can also be directly axiomatized as the (unique) Dedekind-complete ordered field.
I can try to bootstrap the definition of universality from the naturals-to-naturals case, but doing so requires more artificial machinery and is less elegant. I'm wondering whether there's a more &quot;direct&quot; approach. That's why I'm asking for references that discuss how universality is defined in more general domains (than naturals-to-naturals) directly.
Notions like the effective topos and realizability might be relevant.
Several authors have considered this question. If you look at some recent work, it will cite older work. The most recent I am aware of is Pieter Hofstra's and Robin Cockett's work on Turing categories, see Definition 3.1 in their Introduction to Turing categories.