How to construct a single-tape Turing Machine which writes the number 7 in UNARY number system, leaving the tape with a delimiter symbol followed by 7 1s?

So outout would be a tape contains #111111 and blank symbols afterward.


The language you describe is regular (because it's finite), so this can be really straight forward.

You could simple write a 1 and advance to the next state. Create 7 states, one state for each 1.

Consider input\output/direction the syntax for "if input is on the tape write output and move in direction"


  • $\begingroup$ I thought of this at solution at 1st glance actually, but I thought there is a more efficient way of achieving this. Thanks for your effort of course :) $\endgroup$ – CSGuy Dec 14 '15 at 18:54
  • 1
    $\begingroup$ There are small machines that produce a large number of 1's, but to find them is not as easy as it seems. Have you heard of the Busy Beaver problem? $\endgroup$ – André Souza Lemos Dec 14 '15 at 20:21
  • $\begingroup$ Well, you won't be more efficient, because you'd still have at least 7 steps. You could probably find a machine with fewer states, but that get's complicated. $\endgroup$ – Sbls Dec 15 '15 at 16:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.