2020 January 31,

CS 254: Day 12

Carleton College, Joshua R. Davis

A. Problem 2.26.

The remaining problems require you to describe Turing machines. Sometimes students are confused about how much detail to show. So let's be explicit about three possible levels of detail:

  1. At the most detailed level, you draw out the entire Turing machine as a directed graph with annotated edges. For clarity, you may adopt the convention that any missing transition implicitly goes to the reject state. You organize your diagram into sections. You comment those sections, just as you would comment a computer program. You might need to do a rough draft before your final version. Our {am bm cm : m ≥ 0} example in class was done at this level of detail.
  2. At an intermediate level of detail, you do not draw the Turing machine, but you specify exactly how the tape head moves across the tape, how the tape head modifies the tape, and how the Turing machine decides to accept or reject. Usually there is a sequence of left-to-right or right-to-left scans involved. A fellow student, who sees your description at this detail level, should be able to produce a description at detail level 1. See below for an example.
  3. At the least detailed level, you merely state an algorithm, as you would in any other CS course. A fellow student, who sees your description at this detail level, should be able to produce a description at detail level 2 (and then at detail level 1). Most of our course will operate at this level, but we're not there yet.

Here's an example at detail level 2. To understand it, I recommend that you execute it by hand on an example input such as 001001.

Let A = {w w : w is a string in {0, 1}*}. Our decider for A will use an enlarged tape alphabet: In addition to the usual 0, 1, blank, and turnstiles, we will have four symbols 0L, 1L, 0R, 1R. In this way, we can "mark" a 0 or 1 on the tape with an L or R. Now here's the decider.
  1. Wrap the input in turnstiles.
  2. Scan the entire tape left-to-right, marking the first unmarked 0 or 1 with an L.
  3. Scan the entire tape right-to-left, marking the first unmarked 0 or 1 with an R.
  4. Repeat steps 2 and 3 until the left half of the input is marked L and the right half of the input is marked R. During this time, you can also reject if the length of the input is odd.
  5. Scan the entire tape left-to-right, blanking the first L-symbol and the first R-symbol if they agree (0L and 0R or 1L and 1R), or rejecting if they disagree.
  6. Repeat step 5 until all input symbols are blanked. If all goes well, then accept. If any error happens, reject.

B. Draw the {w w : w is a string in {0, 1}*} algorithm just described at detail level 1.

C. Do Exercise 3.8b at detail level 2.