1
$\begingroup$

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)$.

$\endgroup$
2
  • $\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

1
$\begingroup$

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.*

Since

\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*}

and

\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.

$\endgroup$

You must log in to answer this question.

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