HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to show that a non-empty $L$ is recognizable iff there exists a total computable function whose range equals $L$

Submitted by: @import:stackexchange-cs··
0
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?

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$.

Context

StackExchange Computer Science Q#14971, answer score: 2

Revisions (0)

No revisions yet.