Prove that the given function is totally computable

In summary: Then, since the graph of ##f## is recursively enumerable, there must be a computable function ##g(n)## such that for every ##n##, ##g(n)## outputs the pair (##x,y)## such that ##f(x) = y##.
  • #1
Bedrich
6
1
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.
 
  • Like
Likes berkeman
Physics news on Phys.org
  • #2
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?
 
  • Like
Likes Bedrich
  • #3
stevendaryl said:
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.
 
  • #4
Bedrich said:
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?
 
  • Like
Likes Bedrich
  • #5
stevendaryl said:
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)##.
 
  • #6
Bedrich said:
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.
 
  • Like
Likes Bedrich
  • #7
stevendaryl said:
Exactly. And eventually it will.
Thank you very much, but is it proving that ##f## is totally computable? Not just partialy computable?
 
  • #8
Bedrich said:
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##.
 
  • Like
Likes Bedrich

FAQ: Prove that the given function is totally computable

1. What does it mean for a function to be totally computable?

Being totally computable means that the function can be calculated or solved using a finite number of steps or operations. In other words, there exists an algorithm or program that can compute the function's output for any given input.

2. How can you prove that a function is totally computable?

To prove that a function is totally computable, you need to show that there exists an algorithm or program that can compute the function's output for any given input. This can be done by providing a step-by-step procedure or a mathematical formula that can be used to calculate the function's output.

3. What are some examples of totally computable functions?

Some examples of totally computable functions include basic arithmetic operations such as addition, subtraction, multiplication, and division, as well as more complex functions such as logarithms, trigonometric functions, and polynomial equations.

4. Can a function be partially computable?

Yes, a function can be partially computable, meaning that it can be computed for some inputs but not for others. This is often the case for functions that involve infinite or non-terminating processes, such as the halting problem.

5. Why is the concept of total computability important in computer science?

The concept of total computability is important in computer science because it helps us understand the limits of what can be computed by a computer. It also forms the basis for the theory of computability, which is essential for developing efficient algorithms and solving complex problems in various fields such as artificial intelligence, cryptography, and data analysis.

Back
Top