Prove that the given function is totally computable

[Bedrich]

Hello, I'm trying to prove following problem.
1. Homework Statement
Graph of function ƒ : ℕ→ℕ is set {(x, ƒ(x)), x ∈ ℕ and ƒ(x) ≠ ⊥} ⊆ ℕ2. Prove that function ƒ is totally computable when ƒ(x) is defined for every x ∈ ℕ and his graph is recursively enumerable set

Homework Equations

The Attempt at a Solution

I have no idea how to proceed with proving such problem.

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

 

[stevendaryl]

If you know that the graph of $f$ is recursively enumerable, that means that there is a computable function $g(n)$ such that $g(0), g(1), ...$ outputs all the pairs $(x,y)$ such that $f(x) = y$. If you were given such a function $g$, and you were given a value $n$, how would you go about figuring out what $f(n)$ was?

 

[Bedrich]

If you know that the graph of $f$ is recursively enumerable, that means that there is a computable function $g(n)$ such that $g(0), g(1), ...$ outputs all the pairs $(x,y)$ such that $f(x) = y$. If you were given such a function $g$, and you were given a value $n$, how would you go about figuring out what $f(n)$ was?

For every pair $(x, y)$ check if that pair is in the graph and if yes, then $y$ of that pair is $f(n)$? If that is not nonsence.

 

[stevendaryl]

For every pair $(x, y)$ check if that pair is in the graph and if yes, then $y$ of that pair is $f(n)$? If that is not nonsence.

You have a function $g(n)$ which returns a pair $(x,y)$ such that $y = f(x)$. Let's just make something up for example:

$g(0) = (12, 21)$
$g(1) = (34, 72)$
$g(2) = (0, 59)$
etc.
So we know after running $g$ for 3 values that $f(12) = 21$, and $f(34) = 72$ and $f(0) = 59$

So how would you find $f(42)$, for example?

 

[Bedrich]

You have a function $g(n)$ which returns a pair $(x,y)$ such that $y = f(x)$. Let's just make something up for example:

$g(0) = (12, 21)$
$g(1) = (34, 72)$
$g(2) = (0, 59)$
etc.
So we know after running $g$ for 3 values that $f(12) = 21$, and $f(34) = 72$ and $f(0) = 59$

So how would you find $f(42)$, for example?

I would keep running $g(n)$ for every possible $n$ ($g(3), g(4), g(5)$...) until an output pair would be $(42, y)$.

 

[stevendaryl]

I would keep running $g(n)$ for every possible $n$ ($g(3), g(4), g(5)$...) until an output pair would be $(42, y)$.

Exactly. And eventually it will.

 

[Bedrich]

Exactly. And eventually it will.

Thank you very much, but is it proving that $f$ is totally computable? Not just partialy computable?

 

[stevendaryl]

Thank you very much, but is it proving that $f$ is totally computable? Not just partialy computable?

The premise is that "ƒ(x) is defined for every x ∈ ℕ". So for every $x$, there must be a corresponding $y$ such that $f(x) = y$.