Let $\varphi:\mathbb{N}\to\mathbb{N}^*$ be an arbitrary recursive enumeration of finite strings and $\mathcal{I}^n_i(x_1,...,x_n) = x_i $ be the $i$-th projection over $n$ variables.

I would like to show from the point of view of recursion theory that the "variable" projection $$ (n,y) \mapsto \mathcal{I}_y^{\text{len}(\varphi(n))}(\varphi(n)) $$ is recursive.

Using TMs this is quite straightforward: just simulate the TM that computes $\varphi$ and print only the $y$-th term of that TM executed with input $n$. I am interested in a purely "recursion-theoretical" proof, i.e., I would like to know how that function can be written in terms of primitive recursion and/or $\mu$-recursion, which I'm finding tricky.

  • $\begingroup$ I believe this depends on how do you actually formalize "$\varphi$ is recursive". Since this returns a variable-length sequence, and not a single natural, the basic definition of recursive function is no longer applicable. So, how do you choose to formalize that in recursion theory (without TMs)? $\endgroup$ – chi Sep 20 '16 at 12:33
  • $\begingroup$ It can't be recursive because if $y > len(\varphi(n))$, it's undefined. $\endgroup$ – xavierm02 Sep 20 '16 at 14:59
  • $\begingroup$ @xavierm02 Good catch. I guess one would have to default to $n$ or $1$ in that case. $\endgroup$ – Raphael Sep 20 '16 at 19:30
  • $\begingroup$ @chi good point.The basic idea is that $\varphi$ is an effective enumeration of the (finite) strings, i.e. is a bijection and we can compute explicitly the index of each string in finite time (and viceversa). I know, this is actually a TM definition. For the purpose of the question I'm not sure whether it's really necessary to explicitly write $\varphi$ (after all, this "variable projection" returns just a number). Maybe we can rephrase the OP asking whether $\psi:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ that maps $(n,y)$ to the $y$-th symbol of the $n$-th string is recursive. $\endgroup$ – Manlio Sep 20 '16 at 23:59
  • $\begingroup$ @xavierm02 recursive doesn't mean total. If $y>len(\varphi(n))$ it can be undefined but still recursive, i.e. partial recursive. In case you want it to be total, some modifications as the ones suggested by Raphael should work. $\endgroup$ – Manlio Sep 21 '16 at 0:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.