[Math] Turing machine that calculates word’s length

computer scienceturing-machines

The idea of the construction of a composite Turing machine, that (showing to the first symbol of an arbitrary word $w\in \{a,b\}^+$) that writes the length of the word $w$ using the tape letters $0$, $1$ and a blank as a binary number after the word is the following: (The word can be changed during this calculation.)

The input is deleted step by step, where at each time the binary calculator is increased by $1$.
For that the recent binary number is read from right to left, until the first zero is found, that is replaced by $1$.
All previous $1$'s are replaced by $0$'s.
If the recent binary number consists only by $1$, all the $1$'a except of the leftmost one, are replaced by $0$ and on the right an other $0$ is added.

$$$$

I haven't really understood how it works. When we delete a letter of the word, what do we do to increase the binary calculator by $1$ ?

$$$$

EDIT:

In the case at which we want to have the original word at the end of the calculation, one way is the following: the symbols of the word are marked instead of deleted (for example with $a^{\star}$ or $a'$). After the calculation the mark must be deleted.

What exactly does it mean that the TM marks a position? That it overwrites that position?

Best Answer

You correctly describe the successive contents on the tape in the comments: yes, that's exactly what the machine will do.

Now, as to your second question: To mark the symbols in the word you do indeed simply use a different symbol, but from which you can recover the original symbol. So, for example, we can replace an 'a' with an 'A', and a 'b' with a 'B'. As such, the successive contents on the tape will look like this:

$$...abbaabaa...$$

$$...abbaabaA.1.$$

$$...abbaabAa.10.$$

$$...abbaaBaa.11.$$

$$...abbaAbaa.100.$$

$$...abbAabaa.101.$$

$$...abBaabaa.110.$$

$$...aBbaabaa.111.$$

$$...Abbaabaa.1000.$$

$$...abbaabaa.1000.$$

Note that the capital letter will tell the machine which letters it has counted.