How do I show that a (possibly partial) function is computable iff its graph is recursively enumerable?
1
-
3$\begingroup$ We're not especially looking for posts that just consist of the text of an exercise-/practice-style task. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$– D.W. ♦Commented Oct 31, 2023 at 5:30
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Let's say f is partially computable. Then you can bound the number of computational steps. for example if e is the index of the machine which computes f you can define B(S) to be the following set:
{<i,f(i)> | the machine with index e halts and give f(i) as output with i as input in less than S computational steps.}
So graph(f) = U B(S) for all S >= 0.
Since B(S) is recursively enumerable for all S, So is graph(f).
Now, let's say graph(f) is recursively enumerable and you want to compute f(j). You enumerate graph(f)'s members ((According to assumption, there is a machine which can do that)) until you get a member which is in the form <j, k>. Then k is f(j).
