CSE 111, Fall 2004

Homework #6:

Turing-Machine Programs
in Flowchart and Structured Notation

Last Update: 6 October 2004

Note: NEW or UPDATED material is highlighted


  1. The propositional logic connective nand is defined as follows:

    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.
DUE: AT THE START OF LECTURE: WED., OCT 13



Copyright © 2004 by William J. Rapaport (rapaport@cse.buffalo.edu)
file: 111F04/hw06-2004-10-06.html