0
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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"


turingmachine

$\endgroup$
3
  • $\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
    Commented Dec 14, 2015 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$ Commented Dec 14, 2015 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
    Commented Dec 15, 2015 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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