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$ Oct 5, 2015 at 19:01
  • $\begingroup$ It means $(k \cdot x) \cdot y$. $\endgroup$ 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.


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.