Primitive Recursive and Partial Computable Functions: Examples and Counterexamples

The block $1110$ immediately after the initial sentinel has three leading $1$'s before its first $0$, so the decoded sequence length is $3$.

After the first two payload blocks $11010$ and $1110101$, the last block is $101$, which is the self-delimiting block for the binary numeral $1$. Therefore the third decoded coordinate is $1$.

Steps 1.1 and 1.2 show exactly what the theorem [L1] predicts on this concrete input: the primitive-recursive decoders return $\mathrm{len}(s)=3$ and $\mathrm{entry}(s,2)=1$.

The displayed recursion for factorial uses the initial value $1$ and the recursive update $(n,u)\mapsto (n+1)u$, so factorial is a primitive-recursive total function.

Every primitive-recursive function is partial recursive. Applying [L1] to step 1.1 therefore gives a closed lambda term $F$ representing factorial on Church numerals.

Step 1.1 gives the partial-recursive side and step 2.1 gives the lambda-definable side, so factorial is a concrete example of the equivalence asserted in [L1].

By [L1], the function $A$ is total computable.

The same proposition [L1] states that $A$ is not primitive recursive.

Steps 1.1 and 1.2 exhibit one total computable function that fails to be primitive recursive, so $A$ refutes the universal claim stated above.