1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.