0

Hey I am having a hard time trying to make an implementation of a TM (Turing Machine) that describes a list of n strings over {a,b,c,...,z} of max 2n each have a character common to all. Then on top of that, I have to make a complexity class for the TM in terms of n... I don't really know where to start

Nathan Campbell
  • 9
  • First, this question could also appear at computer science stack exchange, although I doubt it's explicitly off topic here.

    Second, the formal description of the turing machine you want is confusing to me. What input does your turning machine get? What do you mean "of max $2n$"? And what do you mean by "make a complexity class"? Do you mean "describe what complexity class the language corresponding to the Turing Machine is in"?

     – Mark Schultz-Wu Apr 30 '18 at 06:14
  • Also, by "common character", do you mean that a character (say $a$) shows up in all strings, or shows up in the same location in all strings? – Mark Schultz-Wu Apr 30 '18 at 06:15
  • yes that is what they are asking. but i can ask the computer science stack exchange if this is the case. – Nathan Campbell Apr 30 '18 at 15:33

0 Answers0