If $T$ is a Turing Machine that accept a language $L$, I want to define a Turing Machine $T'$ such that accepts the language $L^*$.

An approach:

  • $T'$ is a nondeterministic Turing Machine which has many tapes.
  • $T'$ 'copies' in a nondeterministic way a prefix from the original string to another tape and then it is applied $T$

So well, what I should know is:

  1. How many tapes has $T'$ ?
  2. What happens next if $T$ accept this prefix
  3. How is this prefix selected?
  4. What is the end condition to accept a string in $L^*$.
  • $\begingroup$ Could you write a program for recognizing $L*$ in your favorite programming language, if you had a subroutine for recognizing $L$? $\endgroup$ – D.W. Jun 23 '20 at 4:03
  • $\begingroup$ @D.W. I'm pretty sure that I am $\endgroup$ – Eric Toporek Jun 23 '20 at 4:28
  • $\begingroup$ I suggest you edit the question to describe how you'd do that, then figure out how to implement that in a Turing machine only after you've done that. A Turing machine is just a clumsy programming language. $\endgroup$ – D.W. Jun 23 '20 at 5:14

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.