Let $A$ and $B$ be finite alphabets and let $\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^*$ to $B^*$. We say $f$ is computable if there exists a Turing machine $M$ which given an input $x$ in $A^*$, always halts with $f(x)$ on its tape. Let $L_f$ denote the language $\{x\#f(x) \mid x \in A^*\}$. Which of the following statements is true:

Let A and B be finite alphabets and let \# be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*, always halts with f(x) on its tape. Let Lf denote the language \x\#f(x) x A*\. Which of the following statements is true:

Topic-wise GATE CS PYQs with verified steps