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##.