If $\hat{f} : \mathbb{N} \rightarrow \mathbb{N} $ is partial recursive then $f: \Sigma^{*} \rightarrow \Sigma^{*}$ is Turing calculable

Question

I am trying to proof the following statement; If $\hspace{0.2cm}\hat{f} : \mathbb{N} \rightarrow \mathbb{N}$ is partial recursive then $\hspace{0.2cm}f: \Sigma^{*} \rightarrow \Sigma^{*} $is Turing calculable. Where $\hat{f}$ is the Gödel codificadion of $f$. But a I don't have any idea, I don't even know where to start from. Can anyone help me please?

Thanks

Answer 1

I won't write this out in very much detail since the proof is tedious, but the ideas behind it are very simple. Basically, we induct on the construction of a partial recursive function. Fix an alphabet $A=\{\sigma_1,\ldots,\sigma_k\}$. First you need to verify that the three functions

1. $E(x)=\theta$ (erase function)
2. $S_j(x) = x\sigma_j$ (successor function)
3. $P_i^n(x_1,\ldots,x_n)=x_i$ (projection function)

are all TM computable (it should be very easy to write TM programs to do this). Now we need to deal with the operations that are allowed: composition, primitive recursion, and minimization (this is the inductive part of the proof).

1. $f$ is obtained by composition if $f(\bar{x})=g(h_1(\bar{x}),\ldots, h_m(\bar{x}))$, where $\bar{x}=(x_1,\ldots, x_n)$.
2. $f$ is obtained by primitive recursion if $f(\theta,\bar{x})=g(\bar{x})$ and $f(y\sigma_j,\bar{x})=h_j(f(y,\bar{x}),y,\bar{x})$ for $1\le j\le k$.
3. $f$ is obtained by minimization if $f(\bar{x})=\mu_j y(g(y,\bar{x})=\theta)$ (the minimization operator $\mu_j$ denotes the smallest string of $\sigma_j$s that satisfies the expression).

Now for each operation you need to assume there are TM programs that compute the functions $f$ is obtained from, and then construct a TM program from those that computes $f$. Since the class of partial recursive functions is obtained from the three initial functions by finitely many applications of the three operations, this will show that all partial recursive functions are TM computable.