How does one show that the Godel number of $L-$terms are computable?

132 Views Asked by At

I was reading these (page 100 paper pdf) notes and was trying to show the Godel number of $L-$terms are computable. The structural recursion they have for this:

enter image description here

I will use the symbol $g(t) = \ulcorner t \urcorner $ because writing the upper corner brackets in latex is really annoying.

and I wanted to put it in the recursive form that we've shown is computable (it's nearly the same as putting it in primitive recursion):

enter image description here

so I defined $G$ as follows:

$$ G(a,n+1,c)= \begin{cases} \langle SN(v_i) \rangle & (c)_0 = \langle SN(v_i) \rangle, v_i \in Variables \\ \langle SN(F), (c)_1, ... , (c)_n \rangle & o.w. \\ \end{cases} $$

though I noticed that the last line just transalted to:

$$ \langle SN(F), (c)_1, ... , (c)_n \rangle = c $$

which looked extremely silly to me. Since it meant that $G(a,b,c)=c$. What did I do wrong? Is there something I missed?

I notice that this is more of a structural recursion than a normal recursion on natural numbers...so idk if that has to do with the issue.


Context: Definition of computable requested on comments:

Definition of computable is on page 82 paper:

enter image description here

though I had in mind using proposition 5.1.20 and 5.1.21:

enter image description here