1
$\begingroup$

I want to understand how a turing machine that will accept only words of length bigger than 100 will look like. My idea: it will copy a word and move to the right 100 times. If non of the cells was empty it will accept. Furthermore if it is true I can also conclude that it is decidable .

If there is no problem with my assertions so far, how will a turing machine that prints the number of letters in a word will look like? is it possible as well?

$\endgroup$
  • 1
    $\begingroup$ This is, ultimately, a programming question. $\endgroup$ – Raphael Apr 24 '17 at 20:08
  • 1
    $\begingroup$ Everything you can do in C, you can do with a Turing machine. $\endgroup$ – Yuval Filmus Apr 24 '17 at 20:08
  • $\begingroup$ That's funny I haven't considered it. Maybe because I have never really programmed. Can anyone explain how will a turing machine like that will work? and verify if my what I wrote at the beginning is correct and acceptable ? Thank you $\endgroup$ – Akira Apr 24 '17 at 20:13
  • 2
    $\begingroup$ You don't need to copy the word before you move right 100 times. $\endgroup$ – David Richerby Apr 24 '17 at 20:14
  • 1
    $\begingroup$ The Turing machine starts with its input on the tape. $\endgroup$ – David Richerby Apr 24 '17 at 20:20
1
$\begingroup$

Replace every character in the input string with a $1$; you then have the length of the string in unary notation. Then convert the unary representation to your favorite base $b$ by successive division by $b$.

$\endgroup$
1
$\begingroup$

If the target length 100 is fixed, and not an input of the TM, you can simply create a TM with 100 states (beyond the starting and final states), and use those states to effectively "count" up to 100.

Hence, you can just scan the tape once, moving right. If within 100 steps, you find the end of the input, you reject. If after 100 steps the end of the input was not met, you can accept.

$\endgroup$

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.