# Let F be a function from $N ^{n} \longrightarrow N$. Show that if F is computable/ recursive then its graph is computable

Let F be a function from $N ^{n} \longrightarrow N$. Show that if F is computable then its graph is computable.

According to the definition of computable/recursive I am looking at, a relation is computable if its characteristic function is computable. It is also known that the relation of equality is computable. I want to show that given $R(a,b) \leftrightarrow F(a)=b$, the relation R is a computable function.

Here is the definition of computability I am using:

The computable functions are the functions $N ^{n} \longrightarrow N$ obtained inductively by the following rules: (1) $+: N^{2} \longrightarrow N, \cdot: N^{2} \longrightarrow N, \chi _{\leq} : N^{2} \longrightarrow N$ ,and the coordinate functions are computable.

(2) If $G: N^{m} \longrightarrow$ is computable and $H_{1},...H_{m} : N^{n} \longrightarrow N$ are computable the so is the function $F = G(H_{1},...H_{m}) : N^{n} \longrightarrow N$ defined by$F(a)=G(H_{1}(a),...,H_{m}(a))$

(3) If $G : N{n+1} \longrightarrow$ is computable ,and for all $a\in N^{n}$ there exists N such that $G(a,x)=0$, then the function( $F: N^{n} \longrightarrow N$) defined by $F(a)= \mu x(G(a,x)=0)$ is computable.

The graph is computable if its characteristic function is computable.

Thanks for any help

-
Need more definition on computability. What does it mean for a graph to be computable? – user86828 Jul 19 '13 at 21:42
Okay, I put up the definition. Thanks – Jmaff Jul 19 '13 at 21:54
I recommend an appeal to the Church-Turing thesis. – Quinn Culver Jul 22 '13 at 21:24

This sounds good but I am unsure about how your $f(F,y)$ function works. Let's say $F$ has domain and range, $N^{n} \longrightarrow N$. Now the composed function f(F,y) has domain $N^{n+1}$ and range $\{ 0,1\}$ . Thus I think it is more specifically $f(F(x), I_{n+1}^{n+1} (x,y))$ According to our definition of computability (2) though, I thought that the fist coordinate should be a function with domain $N^{n+1}$ Thus I am wondering if there is a way to get $F(x)$ from the n+1 tuple (x,y). – Jmaff Jul 19 '13 at 22:24
I do not understand your confusion. I do not understand what $I_{n+1}^{n+1}$ means. You can get $F(x)$ from the n+1-tuple $(x,y)$. Apply the projection function to it. $F(x_1,x_2 ...) = x_i$ is the projection function and is recursive. Now, the graph of F is defined to be the set of points (x, y) in $N^n \times N = N^{n+1}$ such that $F(x) =y$ The characteristic function of a set of points in $N^{n+1}$ is the function that returns 1 for a point if it is in the set, and 0 if it is not. – user86828 Jul 21 '13 at 18:11
The function $I_{n+1} ^{n+1}(x_{1},...,x_{n+1})$ is the projection function to $x_{n+1}$. I was thinking that one could use the projection function but if I want to apply it to the n+1 tuple (x,y) where $x \in N ^{n}$ then I don't see how to apply projection function to get out an entire n-tuple, namely x. I thought that the projection functions only had single natural numbers as outputs. – Jmaff Jul 21 '13 at 19:50
you can apply the projection function to each part of x. So if $x = (x_1, x_2)...$, and you have the tuple $(x_1, x_2, ... y)$, you can apply one projection function to $x_1$, another to $x_2$, etc. F(x) is really $F(x_1, x_2, x_3...)$. So you compose F with all your projection functions. – user86828 Jul 24 '13 at 18:28