Given a numbering $\varphi_0, \varphi_1, \dotsc$ of the unary partial recursive functions, define a PAS as $\mathbb N$ with application $x \cdot y \simeq \varphi_x(y)$. If the numbering is admissible then this PAS is a PCA.

Is there any non-admissible numbering for which this PAS is a PCA?

Admissible numbering: https://en.wikipedia.org/wiki/Admissible_numbering

PAS = partial applicative structure, a set $X$ together with a binary partial operation $x,y \mapsto x \cdot y$ on $X$, written with left associativity.

PCA = partial combinatory algebra, a PAS such that there is $k,s$ such that (1) $k \cdot x \cdot y = x$, (2) $s \cdot x \cdot y$ is always defined and (3) $s \cdot x \cdot y \cdot z \simeq x \cdot z \cdot (y \cdot z)$.

  • $\begingroup$ What does $k\cdot x\cdot y$ mean? It seems the operation is not associative so that it could mean $k\cdot (x\cdot y) = \varphi_{k}(\varphi_{x}(y))$ or $(k \cdot x)\cdot y = \varphi_{\varphi_{k}(x)}(y)$. See what I mean? $\endgroup$ Commented Oct 5, 2015 at 19:01
  • $\begingroup$ It means $(k \cdot x) \cdot y$. $\endgroup$ Commented Oct 5, 2015 at 20:11

1 Answer 1


There is no recursive non-admissible numbering for which this PAS is a PCA.

Suppose a recursive numbering $\varphi_0, \varphi_1, \dotsc$ forms a PCA. We show that this numbering is admissible by showing that the s-m-n-theorem for $m=n=1$ holds for this numbering.*


\begin{equation*} e, x, y \mapsto \varphi_e(\langle x, y \rangle) \end{equation*}

is partial recursive there is a representative $a$ in the PCA, i.e. an $a$ such that

\begin{equation*} a \cdot e \cdot x \downarrow \end{equation*}


\begin{equation*} a \cdot e \cdot x \cdot y \simeq \varphi_e(\langle x, y \rangle) \end{equation*}

for all natural numbers $e$, $x$ and $y$. Thus

\begin{equation*} s(e,x) = a \cdot e \cdot x \end{equation*}

is a total recursive function such that

\begin{equation*} \varphi_{s(e,x)}(y) \simeq \varphi_e(\langle x, y \rangle). \end{equation*}

*A recursive numbering is admissible if and only if its s-m-n-theorem for $m=n=1$ holds. This is exercise 5.10b on page 26 in:

Soare, Robert I. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. Perspectives in Mathematical Logic. Springer Berlin Heidelberg, 1999.


You must log in to answer this question.

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