I have looked for an answer for this question which seems trivial, but I didn't find any.

Can a Turing machine, given a word $w$, calculate the length of the word?


Yes, of course it can. As a simple intuition, replace "Turing machine" with "computer program" and the answer shouldn't change, assuming that the Church–Turing thesis is true.

Just use a portion of the tape after the input as a binary counter and shuttle back and forth increasing that counter by one for every character in the input, marking the characters that you've already counted.

| cite | improve this answer | |
  • $\begingroup$ Thank you so much. $\endgroup$ – Alan Apr 5 '19 at 15:09

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.