3. Give a one-tape Turing machine M that, given an input string w over alphabet =...

Transcribed Image Text:

3. Give a one-tape Turing machine M that, given an input string w over alphabet = {0, 1}, flips all the bits of w, so each 0 becomes 1 and each 1 becomes 0. At the end of the computation, the tape head should be placed at the first symbol of the output word w. The machine M should accept every input string. For instance, if w = 00101, then at the end of the computation, the string = 11010 should be written on the tape, and the tape head should point to the first symbol of w. See figure below. Input: Output: 001 01 1 0 10 1 0 1 0 You should fully specify M, and in particular, you should fully specify its transition function. 3. Give a one-tape Turing machine M that, given an input string w over alphabet = {0, 1}, flips all the bits of w, so each 0 becomes 1 and each 1 becomes 0. At the end of the computation, the tape head should be placed at the first symbol of the output word w. The machine M should accept every input string. For instance, if w = 00101, then at the end of the computation, the string = 11010 should be written on the tape, and the tape head should point to the first symbol of w. See figure below. Input: Output: 001 01 1 0 10 1 0 1 0 You should fully specify M, and in particular, you should fully specify its transition function.

Answer rating: 100% (QA)

First we use a special symbol to indicate the end of the input string When we move the tape head bac... View the full answer