ASSIGNMENT

$1.$ Consider the given Turing machine. Recall that the input tape contains symbol $\backslash (\backslash$square $\backslash )$ to the left and right of input, and the read$/$write head starts on the left most input position. Create the output for input $10111.$

$2.$ The unary numeral system is a numeral system to represent natural numbers as sequences of ones, that is$,$ to represent a number $\backslash ($ n $\backslash ),$ a symbol representing $"1"$ is repeated $\backslash ($ n $\backslash )$ times. For example, the number $4$ is represented by $1111.$ The number $0$ would be represented by the empty string.

Create a Turing machine which adds $3$ to a natural number, that is$,$ writes three times a $1$ after the given unary number. Afterwards move the head to the left$-$most position of input.

$3.$ Book page $847$ Problem $4$ a

Create a Turing Machine over the alphabet $\backslash (\backslash \{1,\backslash$#$\backslash \}\backslash ))$ that adds two unary numbers together. The numbers will be written on the tape with a $\backslash$# sign separating them. The machine should halt at the left$-$most symbol in the resulting sum.

$4.$ Book page $458$ Problem $5$ i

Give a formal proof for the tautology by using the CP rule. Do not use the IP rule. Note that $\backslash ($ A $\backslash$wedge B $\backslash )$ is a premise for the right$-$hand side and should not be proved.

$\backslash [$

$($A $\backslash$rightarrow C$)\backslash$rightarrow$($A $\backslash$wedge B $\backslash$rightarrow C$)$

$\backslash ]$

$5.$ Book page $457$ Problem $6$ b

Give a formal proof by using the CP rule and by using the IP rule at least once.

$\backslash [$

$($A $\backslash$rightarrow B$)\backslash$wedge$($A $\backslash$vee B$)\backslash$rightarrow B

$\backslash ]$

$6.$ Book page $457$ Problem $7$b

Give a formal proof for each of the following tautologies by using the CP rule and the IP rule and least once. Note that $\backslash ($ A $\backslash$wedge B $\backslash )$ is a premise for the right$-$hand side and should not be proved.

$\backslash [$

$($B $\backslash$rightarrow C$)\backslash$rightarrow$($A $\backslash$wedge B $\backslash$rightarrow A $\backslash$wedge C$)$

$\backslash ]$