Homework #5:

Turing-Machine Programs
for Negation
and Inclusive Disjunction

1. Rewrite the Turing-machine algorithm for negation that we will be doing in class so that the first test after "START" is "1?" (instead of "0?").

   ---

2. Write a Turing-machine algorithm for negation, using the following input-output coding:
   • If the input tape is 0, then the output tape is 1;
   • and if the input tape is 1, then the output tape is 0.

   In other words, both input and output tapes have only one square. Therefore, unlike the version from lecture, there is no record of the original truth value on the output tape; that information has been destroyed during the computation!

   ---

3. Write a Turing-machine algorithm for inclusive disjunction:

   x	y	x or y
   false	false	false
   false	true	true
   true	false	true
   true	true	true

   using the same input-output coding that we will be using in lecture for conjunction, namely:

   • Input:
     • The input tape has two squares, ...
     • ... each containing a 0 or 1 to represent the truth values of two sentences, ...
     • ... and the scanner is over the first square (that is, the leftmost square).

   • Output:
     • The output tape will have three squares: ...
     • ... the original two, unchanged, and a new one (being scanned) containing the truth value of the disjunction.

   Thus, if the input is 01, then the output will be 011.

   ---