# Prove that function is totally computable

The problem that I'm working on is

Graph of function $$f : \mathbb{N}\rightarrow \mathbb{N}$$ is set {$$(x, f(x))$$, $$x \in \mathbb{N}$$ and $$f(x)$$ $$\neq \perp$$} $$\subseteq \mathbb{N}^{2}$$. Prove that function $$f$$ is totally computable when $$f(x)$$ is defined for every $$x$$ $$\in$$ $$\mathbb{N}$$ and his graph is recursively enumerable set.

Do you have any suggestions how to prove it? I have recently started learning theory of computability so some easy to understand answers would be appreciated.

## 1 Answer

Fix a computable enumeration of the graph of the function. On input $$n$$, wait for a pair $$(n,y)$$ to appear in the graph. When you find such a pair, output $$y$$. This is a computable procedure that computes $$f$$.

The totality of the function is irrelevant to this argument. What the procedure shows is that a function $$f$$ is computable if and only if the graph of $$f$$ is computably enumerable.

But if you also know (by your hypothesis) that the function is total, then you've got a total computable function.