I'm having troubles with this question.
If $L\in R$, there there is a turing machine $M$ that decides it. My idea is to build a turing machine $M'$ that somehow goes over all the possible permutations of the input word, in a way that separates it to groups of smaller words for $M$ to test. If there is a permutation that is accepted by all the invoked $M$s, $M'$ should accept this word. (or if it is $\epsilon$)
Since the number of permutations is finite, we can traverse all over them and reject the word eventually, hence $L^*\in R$.
But I'm not sure how to formulate it.

  • 1
    $\begingroup$ The word permutation has a specific meaning in mathematics which differs from the one you implicitly use. $\endgroup$ Commented May 12, 2018 at 17:22
  • $\begingroup$ It seems your basic reasoning is fine. Perhaps you can get some ideas how to formulate the solution by looking at the answers to this related question: Decidable languages kleene star closure - question on a proof. $\endgroup$ Commented May 14, 2018 at 12:15
  • $\begingroup$ It is not always clear what the right formulation is: it depends on the audience, the people that read the solution, and their level of knowledge. So, it might be sufficent to say that the TM guesses a decomposition into subwords, but in other contexts one wants to explain how the TM tests all decompositions, and how to write a TM subroutine that tests a certain substring for membership. The more details, the more tedious it gets. $\endgroup$ Commented May 14, 2018 at 12:16
  • $\begingroup$ @HendrikJan Thanks. I have consulted my TA, and indeed I needed to write a pretty detailed implementation. $\endgroup$
    – porcupine
    Commented May 14, 2018 at 14:53


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.