Different level of description of Turing Machines: ================================ Formal level is what you think it is. The precise states and transition table. It can be expressed as a diagram since it expresses the same information. Implementation level: description of the machine at the level of what exactly is written on the tape, what is, how does the head move. So thangs like "scan the tape until you hit the first '#' symbol, and cross the symbol just to the left of it" is a typical example of what (a part of) implementation level description might look like. High level: this is mre like an algorithmic level, not really caring much about the TM level itself. For example, to give a machine that checks if a string is "left-dominant" (see exercise 1) high level description would probably be "scan the left part of the string and compare (mirror-wise) to the right part, making sure that whenever the left part has 0 the right part has 0 as well. Head behaviour at the end of the tape ===================================== What hapens when the tape tries to move left from the leftmost part of the tape? I understand from Bryce that there was a confusion about that. So the machine simply stays-put in this scenario, (Rather than crashing or doing something else).