[Solved]: Turing-recognizable languages closed under star operation

Problem Detail: 

I'm tasked with demonstrating that the class of Turing-recognizable languages is closed under the operation of star, but I'm confused about how this is true. For example, I have a TM to recognize a language A = { a²ⁿ: n >= 0 }, all strings of a's which length is a power of 2. So here's where I get confused, if I have A*, then I can have (aa)*, which could then lead to (aa)(aa)(aa) = aaaaaa, and this has a length that is not a power of 2. What part of my logic here is wrong?

Asked By : tarrball

Answered By : Luke Mathieson

You're confusing the definition of $A^{\ast}$ and $A$. It is only $A$ in your example that contains strings of $a$s whose lengths are powers of two. $A^{\ast}$ does not have this restriction - it has that restriction that its strings are made up of strings from $A$.

So the individual components of each string in $A^{\ast}$ have to have lengths of powers of two (because they're from $A$), but together we only get that for every string $a^{m}$ in $A^{\ast}$ there is some set $N = \{n_{1},\ldots,n_{k}\}$ (different for each string) such that $m = \sum_{n_{i} \in N} 2^{n_{i}}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33053