Search code examples
complexity-theoryturing-machines

Computability - Can a Turing Machine calculate the input's length?

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?
Solution

  • Yep, certainly! Here’s something to think about:

    • How would you design a TM to increment a binary number?
    • How could you use that other TM as a subroutine to count the input length?

    Another perspective: remember that by the Church-Turing thesis anything you can do with any effective model of computation you can do with a TM, so since other models can measure input length, TMs can do it as well.