1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The word permutation has a specific meaning in mathematics which differs from the one you implicitly use. $\endgroup$ – Yuval Filmus May 12 '18 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$ – Hendrik Jan May 14 '18 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$ – Hendrik Jan May 14 '18 at 12:16
  • $\begingroup$ @HendrikJan Thanks. I have consulted my TA, and indeed I needed to write a pretty detailed implementation. $\endgroup$ – porcupine May 14 '18 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.