3
$\begingroup$

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 "universal function"

I suppose we could define "universal function" 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 "axiomatic", "abstract", and "generic" 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 "direct" 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.

$\endgroup$
7
  • $\begingroup$ What is your definition of universal function? $\endgroup$ Jan 22 at 9:08
  • $\begingroup$ @YuvalFilmus Added. $\endgroup$
    – user76284
    Jan 22 at 21:23
  • 1
    $\begingroup$ So you're asking whether these two definitions are equivalent? Have you tried proving that they are? $\endgroup$ Jan 22 at 21:24
  • $\begingroup$ @YuvalFilmus See the addendum for the motivation. $\endgroup$
    – user76284
    Jan 22 at 21:37
  • $\begingroup$ The universal function $u$ is supposed to take two arguments, at least according to the definition you linked to. But the one in your question takes a single argument. This should be sorted out. $\endgroup$ Jan 23 at 7:39
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.