Let be the following statement. For every computable function f: {0, 1}* {0, 1}*, there is...

Transcribed Image Text:

Let be the following statement. For every computable function f: {0, 1}* {0, 1}*, there is a computable function g {0,1} {0, 1}* such that, for all r = {0,1}*, g(f(x)) = x. (a) Prove that is false by giving a counterexample. (b) Strengthen the hypothesis of just enough to obtain a statement ' that is true. (c) Prove your statement '. Let be the following statement. For every computable function f: {0, 1}* {0, 1}*, there is a computable function g {0,1} {0, 1}* such that, for all r = {0,1}*, g(f(x)) = x. (a) Prove that is false by giving a counterexample. (b) Strengthen the hypothesis of just enough to obtain a statement ' that is true. (c) Prove your statement '.