snippetMinor
How to show that a non-empty $L$ is recognizable iff there exists a total computable function whose range equals $L$
Viewed 0 times
totalshowcomputablewhosenonexistsrangeemptyrecognizablefunction
Problem
This almost makes sense to me, but I feel like I'm missing something.
I know that for a decidable language, there must exist some total computable function $f$ that can take in any $x \in \sum^{*}$ and tell us whether or not $x$ is accepted (while my textbook is unclear, I would infer from this that decidable languages and computable functions are equivalent?)
So I can see that $L$ is decidable if and only if some computable function can determine if $x \in L$ or not, which implies the existence of a function $f(x)$ that outputs $x$ if $x \in L$, and nothing otherwise (this makes sense in my head at least...correct me if I'm wrong). How would I use what's given to show that this is true for any recognizable $L$ though? Computable functions have finite steps have to halt, from my understanding, so how that they be used to check if $x$ belongs to a recognizable but undecidable language?
I know that for a decidable language, there must exist some total computable function $f$ that can take in any $x \in \sum^{*}$ and tell us whether or not $x$ is accepted (while my textbook is unclear, I would infer from this that decidable languages and computable functions are equivalent?)
So I can see that $L$ is decidable if and only if some computable function can determine if $x \in L$ or not, which implies the existence of a function $f(x)$ that outputs $x$ if $x \in L$, and nothing otherwise (this makes sense in my head at least...correct me if I'm wrong). How would I use what's given to show that this is true for any recognizable $L$ though? Computable functions have finite steps have to halt, from my understanding, so how that they be used to check if $x$ belongs to a recognizable but undecidable language?
Solution
Hints:
-
If $L$ is recognized by some Turing machine $T$, then consider a Turing machine that on input $(x,n)$, runs $T$ on $x$ for $n$ steps and outputs $x$ if $T$ halts within $n$ steps.
-
If $L$ is enumerated by some Turing machine $T$, then given $x$, accept it if it appears in the list generated by $T$.
-
If $L$ is recognized by some Turing machine $T$, then consider a Turing machine that on input $(x,n)$, runs $T$ on $x$ for $n$ steps and outputs $x$ if $T$ halts within $n$ steps.
-
If $L$ is enumerated by some Turing machine $T$, then given $x$, accept it if it appears in the list generated by $T$.
Context
StackExchange Computer Science Q#14971, answer score: 2
Revisions (0)
No revisions yet.