Let < M > be an encoding of a Turing machine.

L = { < M > | M is a Turing machine that accepts a string of length 2014 }

Above language is R.E(even though we have infinite TM's) as we have finite amount of strings of length 2014 and we can apply dovetailing method.

My doubt is can we apply dovetailing if we have infinite number of strings and infinite number of Turing machines ?

  • $\begingroup$ Sure. Dovetail twice. $\endgroup$ – Raphael Jan 22 '18 at 7:56
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jan 22 '18 at 7:56
  • $\begingroup$ If possible can you please elaborate it ? I think that we can run first string on first machine for 1 step. Then first string and second string on machine 1 and 2 for one more step. Then, First,second and third string on machine 1,2,3 for one more step each and so on... Is it correct? @Raphael. $\endgroup$ – Rajesh R Jan 22 '18 at 8:41
  • 2
    $\begingroup$ I think you can answer your own question now. $\endgroup$ – Yuval Filmus Jan 22 '18 at 18:43

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.