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 * stopHere 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 ... => ...
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| |