2018 October 1,
Carleton College, Joshua R. Davis
A. Problem 2.26.
B. In class, we've outlined how to construct a Turing machine to decide the language A = {an bn cn : n ≥ 0}. For your homework, draw out this entire Turing machine. Include every arrow, and handle every error condition. For clarity, organize your diagram into sections, and annotate those sections, just as you would comment a computer program. (However, your Turing machine should not be broken into disconnected sections. All of its parts should connect into a single diagram.) This is probably the only time in our course when I will ask you to draw an entire non-trivial Turing machine.