A Turing machine uses a read-write head that traverses the squares of an unbounded roll of toilet paper, where only a 0 or a 1 can be written in a square:


The controller can be wired as a "processor" that understands these six instructions:

* move Left/Right one square
* erase the square (make it blank)
* write 0/1 on the square
* if square is blank/0/1, then goto Instruction #n
* goto Instruction #n
* stop
Here is a sample program that scans a binary number from left to right and flips all 0s to 1s and all 1s to 0s:

#1: if square is 0, then goto #4
#2: if square is 1, then goto #6
#3: if square is blank, then goto #9
#4: write 1
#5: goto #7
#6: write 0
#7: move Right
#8: goto #1
#9: stop

 ... => ... 

Exercise

Use the instructions for the Universal Turing Machine to write a program for it that will read a binary int and add one to it. The machine starts at the first blank square to the left of the int,
 V
| |1|0|1|1| |   and it moves to the right of the int, 
                till it finds the rightmost digit:
         V             
| |1|0|1|1| |   Then it adds one and does the needed carries 
                until it is finished:
     V                                                      V
| |1|1|0|0| |   Finally, it resets to its start position:  | |1|1|0|0| |