Homework #6:

Turing-Machine Programs
in Flowchart and Structured Notation

1. The propositional logic connective nand is defined as follows:
   
   THIS WAS STATED INCORRECTLY IN THE VERSION ANNOUNCED IN LECTURE. I HAVE INDICATED THE CHANGES IN CAPITAL LETTERS.

   The truth value of "x nand y" is FALSE if the truth values of x and of y are both TRUE; otherwise, the truth value of "x nand y" is TRUE. (In other words, "x nand y" is logically equivalent to "not (x and y)".)

   Write a TM program in flowchart notation that computes the truth table for nand. Let the input tape consist of two squares, each containing a binary representation for the truth value of one of the input propositions, with the first square being scanned. Let the output tape consist of three squares, the first two containing the input, and the third containing the truth value of the nand of the inputs, with the third square being scanned.

2. Translate that program into structured notation (like the structured program for conjunction).

   Hints:

   1. First label the arrows in the flowchart with names of Turing-machine states (M0, M1, etc.). You don't have to label the "true" and "false" arrows that come out of test diamonds.

   2. The outline of your structured program should be:
      1. START;
      2. Keep doing whichever of the following you can:
         list of commands;
      3. STOP

   3. The list of commands should include 1 command for each possible combination of state and scanned symbol.

   4. Each such command should be of the form:
      if state = M and test is true then
        begin
          TM instruction;
          go to next state
        end;

   5. The test "test is true" could be any of the following:
      • scanning s, where "s" is either "0" or "1".
      • scanning the left end of the tape
      • not scanning the left end of the tape
      • scanning the right end of the tape
      • not scanning the right end of the tape

   6. And each TM instruction is one of:
      • LEFT
      • RIGHT
      • PRINT-0
      • PRINT-1
      • ERASE

3. Write another TM program in flowchart notation that also computes the truth table for nand. As before, let the input tape consist of two squares, each containing a binary representation for the truth value of one of the input propositions, with the first square being scanned. But this time, let the output tape consist of one square containing the truth value of the nand of the inputs, with that square being scanned.

4. Translate that program into structured notation.