You should finish working through Lab 13 if you haven't already done so. Also, finish reading the two handouts from class (Proof or Consequences and Conversations with Gödel).
It turns out that we can build any digital circuit whatsoever out of just NAND gates. In other words, AND, OR, NOT, and all the other logic gates can be replaced by particular combinations of NAND gates. Show how to build separate AND, OR, and NOT circuits using only NAND gates.
The Turing Machine shown below requires its input to begin with a 0 in the leftmost position of the tape, followed by the binary representation of a number, followed by blanks. Trace through the execution of the machine by hand, for the following input strings, showing the final contents of the tape after the machine halts. Assume that the machine always starts in state 1.
What mathematical operation does this machine perform on its input?
Tape symbols: 0 1 b Start state: 1 Halt state: 4 ----------------------------------------------------------------------- Rule # State Symbol New state New symbol Move ----------------------------------------------------------------------- (1) 1 0 1 0 R (2) 1 1 1 1 R (3) 1 b 2 b L (4) 2 0 4 1 R (5) 2 1 3 0 L (6) 3 0 4 1 R (7) 3 1 3 0 L -----------------------------------------------------------------------
Design a Turing Machine that multiplies a binary number by 8. Assume the input tape will contain a binary number written as a sequence of 0's and 1's, followed by blanks. Hint: Remember that appending a single 0 to the end of a binary number effectively multiplies it by 2, so to multiply by 8, just append 000. For example, binary 101 (5 in decimal) times 8 yields 101000 (40 in decimal). Fill in the rule table below for your machine, or use another sheet of paper if you need more room.
Tape symbols: 0 1 b Start state: Halt state: ----------------------------------------------------------------------- Rule # State Symbol New state New symbol Move ----------------------------------------------------------------------- -----------------------------------------------------------------------
The Proof or Consequences handout describes "Busy Beaver" Turing machines on pages 344-346. Busy Beavers start with a completely blank tape and write as many 1's on the tape as possible before halting. The number of 1's they can write depends on how many internal states they have available. For example, a Busy Beaver with three internal states (A, B, and C) is shown on page 345 of the handout. This machine writes six 1's on its tape before halting. A machine with only two states can write a maximum of four 1's. Design a two-state machine to do this, by writing out the rule table for it as in question 3 above.
Write out all of your answers on paper and turn this in during class.