1
$\begingroup$

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:

  • enter image description here

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?

$\endgroup$
  • $\begingroup$ What is $\phi_x$ in Rogers' book? $\endgroup$ – Asaf Karagila May 22 at 1:28
  • $\begingroup$ Also, you may have mistyped the definition from Rogers' book, as you write $U\colon N\times N\times N$, rather than $U\colon N\times N\to N$. $\endgroup$ – Asaf Karagila May 22 at 1:30
  • $\begingroup$ @AsafKaragila $\phi_x$ is the function defined by the program (=number) $x$. Thanks, I fixed the typo. $\endgroup$ – user634426 May 22 at 1:31
1
$\begingroup$

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(f(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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Here's the exact theorem from Rogers' book: i.stack.imgur.com/Y65xI.png So he says that a universal function is $\phi_z$ from Theorem IV. I replaced $\phi_z$ by "computable $U$" (as far as I understand, "computable $U$" amounts to saying that $U=\phi_z$ for some $z$, so I thought I stated it in an equivalent way; or did I not express what Rogers means correctly?) As for the second definition, it is equivalent to the third, and the authors of the third definition make a distinction between a universal function and Gödel universal function: i.stack.imgur.com/a9hTc.png $\endgroup$ – user634426 May 26 at 2:55
  • $\begingroup$ And here's the part about fixing a numbering from Rogers' book: i.stack.imgur.com/FQUfq.png Correction of the previous comment: the third definition isn't equivalent to the first, as I mentioned in the question, but the author of the lecture notes where I've taken it from also makes the distinction between a universal function and Gödel universal function, just like the authors of the third definition. $\endgroup$ – user634426 May 26 at 3:01
  • $\begingroup$ Did you take a look at the original Rogers' statement/definition above? And if so, do you still think it's silly (i.e., did I transcribe it correctly)? Also, one thing keeps bothering me about non-Rogers' definition of universal function or acceptable numbering. This must be something trivial, but I don't get it. These definitions don't say that the meaning of $U(p,x)$ is "the result of application of the program with number $p$ on the argument $x$". I'm pretty sure it's eiher assumed or follows somehow from the definition, but I don't see why. $\endgroup$ – user634426 May 27 at 1:35

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.