patternMinor
recursive language and computable function
Viewed 0 times
computablefunctionlanguagerecursiveand
Problem
Question:
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 $\Bigl \{x\# f(x) \mid x\in A^{} \Bigr \}$. Which of the following statements is true:
(A) $f$ is computable if and only if $L_{f}$ is recursive.
(B) $f$ is computable if and only if $L_{f}$ is recursively enumerable.
(C) If $f$ is computable then $L_{f}$ is recursive, but not conversely.
(D) If $f$ is computable then $L_f$ is recursively enumerable, but not conversely.
My Attempt:
if $f$ is computable then given $x$ on tape of TM, it will always halt in $f(x)$ on Tape.
$L_f$ denote the language $\Bigl \{x\# f(x) \mid x\in A^{*} \Bigr \}$, which means $L_f$ strings of type which has image and pre image to left and right of $\#$.
Yes, $L_f$ wil be recursive if $f(x)$ is computable. Because if $x\# f(x)$ is given then i will first convert $x$ in $f(x)$ (i can do it because $f(x)$ is computable ) this gives me $f(x)\# f(x)$ on table and i just left to match left strings to the right string of $\#$ .
(i need exlanation of this part)
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 $\Bigl \{x\# f(x) \mid x\in A^{} \Bigr \}$. Which of the following statements is true:
(A) $f$ is computable if and only if $L_{f}$ is recursive.
(B) $f$ is computable if and only if $L_{f}$ is recursively enumerable.
(C) If $f$ is computable then $L_{f}$ is recursive, but not conversely.
(D) If $f$ is computable then $L_f$ is recursively enumerable, but not conversely.
My Attempt:
if $f$ is computable then given $x$ on tape of TM, it will always halt in $f(x)$ on Tape.
$L_f$ denote the language $\Bigl \{x\# f(x) \mid x\in A^{*} \Bigr \}$, which means $L_f$ strings of type which has image and pre image to left and right of $\#$.
- Now consider a function $f(x)$ is computable and its corresponding language $L_f$, will $L_f$ be recursive ? (given that $f(x)$ is computable )
Yes, $L_f$ wil be recursive if $f(x)$ is computable. Because if $x\# f(x)$ is given then i will first convert $x$ in $f(x)$ (i can do it because $f(x)$ is computable ) this gives me $f(x)\# f(x)$ on table and i just left to match left strings to the right string of $\#$ .
- Now consider a function $L_f$ is recursive, will $f(x)$ be computable ?
(i need exlanation of this part)
Solution
The question is about the relation between a computable function $f$ and its graph (here denoted by $L_f$).
Since the function is total, the function is computable if and only if its graph is recursive (in case $f$ is a partial computable function, $f$ is computable if and only if its graph is r.e.).
So, your guess is right, and the correct answer is A.
To compute $f$ from the characteristic function of the graph, you need to use a generate and test technique, progressively trying all possible outputs y for a given input x (using the characteristic function as tester), until you find the correct pair x#y. Since such a pair must exist, your algorithm is terminating.
Since the function is total, the function is computable if and only if its graph is recursive (in case $f$ is a partial computable function, $f$ is computable if and only if its graph is r.e.).
So, your guess is right, and the correct answer is A.
To compute $f$ from the characteristic function of the graph, you need to use a generate and test technique, progressively trying all possible outputs y for a given input x (using the characteristic function as tester), until you find the correct pair x#y. Since such a pair must exist, your algorithm is terminating.
Context
StackExchange Computer Science Q#70626, answer score: 5
Revisions (0)
No revisions yet.