for Turing machines to an instance of the word problem. Concretely, Post devised an encoding as a finite string of the state of a Turing machine plus tape, such that the actions of this machine can be carried out by a string rewrite system acting on this string encoding. The alphabet of the encoding has one set of letters for symbols on the tape (where means blank), another set of letters for states of the Turing machine, and finally three letters that have special roles in the encoding. and are intuitively extra internal states of the Turing machine which it transitions to when halting, whereas marks the end of the non-blank part of the tape; a machine reaching an should behave the same as if there was a blank there, and the was in the next cell. The strings that are valid encodings of Turing machine states start with an , followed by zero or more symbol letters, followed by exactly one internal state letter (which encodes the state of the machine), followed by one or more symbol letters, followed by an ending . The symbol letters are straight off the contents of the tape, and the internal state letter marks the position of the head; the symbol after the internal state letter is that in the cell currently under the head of the Turing machine. A transition where the machine upon being in state and seeing the symbol writes back symbol , moves right, and transitions to state is implemented by the rewrite whereas that transition instead moving to the left is implemented by the rewrite with one instance for each symbol in that cell to the left. In the case that we reach the end of the visited portion of the tape, we use instead , lengthening the string by one letter. Because all rewrites involve one internal state letter , the valid encodings only contain one such letter, and each rewrite produces exactly one such letter, the rewrite process exactly follows the run of the Turing machine encoded. This proves that string rewrite systems are Turing complete. The reason for having two halted symbols and is that we want all halting Turing machines to terminate at the same total state, not just a particular internal state. This requires clearing the tape after halting, so eats the symbol on it left until reaching the , where it transitions