# Proving reducibility of a language to another language [duplicate]

I am self-studying formal languages and want to solve an example problem. Given formal languages $A,B\subset\Sigma^*$ over an alphabet $\Sigma=\{a,b,c\}$ with $$A=\{\omega\in\Sigma^*\vert\left|\omega_a\right|=\left|\omega_b\right|=\left|\omega_c\right|\}$$ and $$B=\{a^ib^jc^k\vert i,j,k\in\mathbb{N}\}$$ where $\left|\omega_n\right|$ denotes the number of $n$s in the word $\omega\in\Sigma^*$, I want to prove that $A$ is reducible to $B$, i.e. that there exists a computable (total) function $f:\Sigma^*\rightarrow\Sigma^*$ for which it holds that $\omega\in A\iff f(x)\in B$ for all words $\omega\in\Sigma^*$.

I think a suitable function would be given by $f(\omega):=abca^{\vert\left|\omega_a\right|-\left|\omega_b\right|\vert}b^{\vert\left|\omega_b\right|-\left|\omega_c\right|\vert}$, for which the required equivalence obviously holds. But it is not clear to me how I would best prove that this function is (Turing-)computable. Do I have to produce an explicit Turing machine which takes a word $\omega$ as input and outputs $f(\omega)$, or is there a more straightforward way? Also, is there a way to intuitively see that this function is computable?

• Both languages are computable, so there is such a function -- that's a rather easy lemma. The proof is illustrative; a suitable $f$ is completely boring. See also here; despite the different setting, the answer is literally the same. (If your problems can be solved by functions that are not more powerful than the reduction, this always works.) Mar 23, 2018 at 14:25
• @Raphael How do I prove that the function $f$ I gave is computable though. I want to understand this as well. Mar 24, 2018 at 13:13
• @Raphael In fact, this was my primary question. I only wrote down the rest of the exercise to provide context. Should I edit the question, make a new one, or can you answer me here in the comments please. Mar 24, 2018 at 14:40
• I see. "Do I have to produce an explicit Turing machine which takes a word ω as input and outputs f(ω), or is there a more straightforward way?" -- that's the definition, so yes. Helpful lemmas may exist, and depending on your level you may be willing to hand-wave more or less. Basically, give an algorithm at the appropriate level of precision that computes $f$. Mar 25, 2018 at 16:55