1. We have assumed that a Turing machine can detect the left end of its tape. One way this can be done (without adding it as a "feature" of the TM) is to insert a special left-end-of- tape marker symbol Formally describe a TM that does the following. It starts with some string w {a,b)" on its input tape. It should halt with "> w" on its tape and its head on the first character of w. Here is just a new tape symbol. The idea is that this TM could be used as a convenient initialization subroutine," after which you can always detect the left end of the tape from the symbol. start halt Describe your TM using a complete transition table, like the one used in Nov 17 lecture Give your states human-readable names. Of course you should not assume that you can detect the left end of the tape (chicken & egg problem)