12. In this question, we explore the equivalence between function computation and language recognition as performed by Turing machines. For simplicity, we will consider only functions from the nonnegative integers to the nonnegative inte- gers (both encoded in binary). But the ideas of these questions apply to any com- putable function. We'll start with the following definition: Define the graph of a function fto be the set of all strings of the form [x.fx)], where x is the binary encoding of a nonnegative integer, and flx) is the binary encoding of the result of applyingfto x For example. the graph of the function succ is the set ([o, 1].[1. 101,[10,11]...) a. Describe in clear English an algorithm that, given a Turing machine M that computes f, constructs a Turing machine M' that decides the language L that contains exactly the graph of f. b. Describe in clear English an algorithm that, given a Turing machine M that decides the language L that contains the graph of some function f.constructs a Turing machine M' that computes f. c A function is said to be partial if it may be undefined for some arguments. If we extend the ideas of this exercise to partial functions, then we do not require that the Turing machine that computes fhalt if it is given some input x for which fix) is undefined. Then L (the graph language for f), will contain entries of the form [r.Jx)] for only those values of x for which fis defined.In that case, it may not be possible to decide L, but it will be possible to semidecide it. Do your construc- tions for parts (a) and (b) work if the function fis partial? If not, explain how you could modify them so they will work correctly. By"work", we mearn: For part (a): Given a Turing machine that computes f) for all values on which fis defined, build a Turing machine that semidecides the language L that contains exactly the graph of f. For part (b): Given a Turing machine that semidecides the graph language of f (and thus accepts all strings of the form[x, f(x)] when f(r) is defined) build a Turing machine that computes f