Quelle: http://math.hws.edu/TMCM/java/labs/xTuringMachineLab.html

Exercise 1: Create a Turing machine that will move to the right until it finds a $. Then it will erase everything on the tape between that $ and the next $ to the right. It will halt when it gets to the second $. The $'s themselves should not be erased. You can do this with a fairly simple machine that uses only two states, 0 and 1. (Note that if the machine is started on a tape that does not contain two $'s to the right of the machine's starting position, then the machine will never halt.)

Exercise 2: One of the examples in the lab is a Turing machine called "FindDoubleX." This machine moves to the right until it comes to two x's in a row. Then it halts on the first of the two x's. Create a new machine that will move to the right until it finds three x's in a row. It should halt when it finds a group of three consecutive x's. (Ideally, it should move back to the first of the three x's and halt there.)

Exercise 3: This exercise assumes that you have done Exercise 2. Given any sequence of x's, y's, and z's, describe how you could construct a machine that will move to the right until it finds the given sequence. For example, if the sequence is xyzzyx, it should move to the right until it has found the symbols x, y, z, z, y, and x in consecutive squares, and then it should halt. What is the minimum number of states that such a machine would need (assuming that you don't care which square it halts on)? Why?

Exercise 4: Construct a Turing machine to do the following: Assume that the machine is started on a tape that contains nothing but a string of $'s. The machine is started on the left end of this string. The purpose of the machine is to multiply the length of the string by 3. For example, if it is started on a string of seven $'s, it should halt with twenty-one $'s on the tape. If it is started on a string that contains just one $, it should halt with three $'s on the tape. Here is one way that the machine might operate: Change one of the $'s to an x, then go to the end of the string and write two more x's. Go back and process the next $ in the same way. Continue until all the $'s have been processed. Then change all the x's to $'s.