In this exercise we explore the equivalence between function computation and language recognition for Turing machines. For simplicity, we shall consider only functions from nonnegative integers to nonnegative integers, but the ideas of this problem apply to any computable functions. Here are the two central definitions$:$
- Define the graph of a function $f$ to be the set of all strings of the form, $\left [x,f(x) \right ],$ where $x$ is a nonnegative integer in binary, and $f(x)$ is the value of function $f$ with argument $x,$ also written in binary.
- A Turing machine is said to compute function $f$ if, started with any non -negative integer $x$ on its tape, in binary, it halts $($in any state$)$ with $f(x),$ in binary, on its tape.
Answer the following, with informal, but clear constructions.
- Show how, given a TM that computes $f,$ you can construct a TM that accepts the graph of $f$ as a language.
- Show how, given a TM that accepts the graph of $f,$ you can construct a TM that computes $f.$
- 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 TM computing $f$ halts if it's input $x$ is one of the integers for which $f(x)$ is not defined.Do your constructions for parts $(a)$ and $(b)$ work if the function $f$ is partial$?$ If not, explain how you could modify the construction to make it work.
