Recursion, Truncation, and "coding."

Question

The example is "left to the reader", but I am having trouble approaching this problem.

There is a primitive recursive function $tr$ such that if $s$ codes a sequence $(a_{0},...,a_{n-1})$, and $m\le n$, then $tr(s,m)$ codes the truncated sequence $(a_{0},...,a_{m-1})$

How does one go about showing that this is primitive recursive? My text defines primitive recursion as follows $$h(x,0)=f(x),h(x,s(y))=g(x,y,h(x,y)).$$

Thank you for any help in advance!

Edit: The text says "The coding we adopt is based on the fact that each positive interger can be written in one and only one way as a product of powers of larger and larger primes. Specifically: $(a_{0},...,a_{n-1})$ is coded by $2^{n}\cdot 3^{a_{0}} \cdot 5^{a_{1}}\cdots \pi (n)^{a_{n-1}}$"

Answer 1

We need an encoding scheme for a sequence $\langle a_0, \ldots, a_{n-1} \rangle$ of numbers.

According to BBJ's encoding, page 79 :

$s= 2^n3^{a_0} \ldots \pi(n)^{a_{n-1}}$

With this encoding, we have that :

$lh(s)=lo(s,2)$, where $lo(x,y)$ is the greatest $z ≤ x$ such that $y^z$ divides $x$ if $x, y > 1$,

i.e. the "lenght" of $s$,

and :

$ent(s,i)=lo(s,\pi(i+1))$, for $0 < i <n$,

i.e. $ent(s,i)=a_i$,

are the "deconding" functions.

Thus:

$tr(s,m)=2^m\Pi_{0 < i < m} \pi(i)^{ent(s,i)}$

Answer 2

The base case

$tr(s, 0) = first(s)$

The recursive case

$tr(s, m) = first(s) \oplus tr(rest(s), m - 1)$

Where $first(s)$ returns the first item in a list $s$

and

$rest(s)$ returns a list of everything but the first element

$\oplus $ appends lists