In this assignment, you will design a Turing Machine that computes a function similar to the

length $()$ function in Java, or the len$()$ function in Python.

To make it simpler, the len$()$ function returns the result as a binary string.

To be consistent with the simulator, we assume the following:

The TM has a two$-$way infinite tape that contains the input

The input is the argument to the function, and the TM starts with its head scanning the first symbol of the input. If the input is the empty string, then the tape is all blank.

The TM has a halt state.

The result of the computation is derived from the contents of the tape when it reaches the halt state. The result is the string starting at the first non$-$blank symbol and ending at the last non$-$blank symbol. If the tape is all blank, the result is the empty string. The input to the TM should no longer be on the tape.

To make it simpler, we will assume the input is a string over alphabet $\{$a$,$b$\}.$ Your Turing machine should compute the length of the input and write it on the tape in decimal. The original input should no longer be on the tape when the TM halts.

Give a high level description of your Turing machine. $($This level of description is like pseudo$-$code and ignores implementation details.$)$

Give a formal description of your Turing machine by providing a Turing machine program that can be executed