# Can a turing machine calculate word's length?

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?

• This is, ultimately, a programming question.
– Raphael
Apr 24 '17 at 20:08
• Everything you can do in C, you can do with a Turing machine. Apr 24 '17 at 20:08
• 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 Apr 24 '17 at 20:13
• You don't need to copy the word before you move right 100 times. Apr 24 '17 at 20:14
• The Turing machine starts with its input on the tape. Apr 24 '17 at 20:20

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$.