Turing Machine algorithms

I take it that 11111111 is like an opcode and 0001, 0001 are the operands for that opcode. At least, that's the only interpretation I am seeing.

A TM can look for a fixed, finite number of symbols by using a similar fixed, finite number of states, the sole purpose of each one being to recognize that another of the expected symbols has been seen. For instance, here's a four-tape TM that recognizes addition and does the binary addition:

|----|----|----|----|----||----|-----|-----|-----|-----|----|----|----|----| | Q | T1 | T2 | T3 | T4 || Q' | T1' | T2' | T3' | T4' | D1 | D2 | D3 | D4 | |----|----|----|----|----||----|-----|-----|-----|-----|----|----|----|----| // read the opcode ///////////////////////////////////////////////////////// | qA | 1 | x | y | z || qB | 1 | x | y | z | R | S | S | S | | qB | 1 | x | y | z || qC | 1 | x | y | z | R | S | S | S | | qC | 1 | x | y | z || qD | 1 | x | y | z | R | S | S | S | | qD | 1 | x | y | z || qE | 1 | x | y | z | R | S | S | S | | qE | 1 | x | y | z || qF | 1 | x | y | z | R | S | S | S | | qF | 1 | x | y | z || qG | 1 | x | y | z | R | S | S | S | | qG | 1 | x | y | z || qH | 1 | x | y | z | R | S | S | S | | qH | 1 | x | y | z || qI | 1 | x | y | z | R | S | S | S | // read the first addend /////////////////////////////////////////////////// | qI | w | x | y | z || qJ | w | w | y | z | R | R | S | S | | qJ | w | x | y | z || qK | w | w | y | z | R | R | S | S | | qK | w | x | y | z || qL | w | w | y | z | R | R | S | S | | qL | w | x | y | z || qM | w | w | y | z | R | R | S | S | // read the second addend ////////////////////////////////////////////////// | qM | w | x | y | z || qN | w | x | w | z | R | S | R | S | | qN | w | x | y | z || qO | w | x | w | z | R | S | R | S | | qO | w | x | y | z || qP | w | x | w | z | R | S | R | S | | qP | w | x | y | z || qQ | w | x | w | z | R | S | R | S | // prepare the output tape ///////////////////////////////////////////////// | qQ | w | x | y | z || qR | w | x | y | z | S | S | S | R | | qR | w | x | y | z || qS | w | x | y | z | S | S | S | R | | qS | w | x | y | z || qT | w | x | y | z | S | S | S | R | | qT | w | x | y | z || qU | w | x | y | z | S | S | S | R | // handle addition when no carry /////////////////////////////////////////// | qU | w | 0 | 0 | z || qU | w | 0 | 0 | 0 | S | L | L | L | | qU | w | 0 | 1 | z || qU | w | 0 | 1 | 1 | S | L | L | L | | qU | w | 1 | 0 | z || qU | w | 1 | 0 | 1 | S | L | L | L | | qU | w | 1 | 1 | z || qV | w | 1 | 1 | 0 | S | L | L | L | | qU | w | B | B | B || hA | w | B | B | B | S | R | R | R | // handle addition when carry ////////////////////////////////////////////// | qV | w | 0 | 0 | z || qU | w | 0 | 0 | 1 | S | L | L | L | | qV | w | 0 | 1 | z || qV | w | 0 | 1 | 0 | S | L | L | L | | qV | w | 1 | 0 | z || qV | w | 1 | 0 | 0 | S | L | L | L | | qV | w | 1 | 1 | z || qV | w | 1 | 1 | 1 | S | L | L | L | | qV | w | B | B | B || hA | w | B | B | B | S | R | R | R | |----|----|----|----|----||----|-----|-----|-----|-----|----|----|----|----| 

Legend:

• Q: current state
• T1: current tape symbol, input tape
• T2: current tape symbol, scratch tape #1
• T3: current tape symbol, scratch tape #2
• T4: current tape symbol, output tape (not used)
• Q': state to transition into
• T1': symbol to write to input tape (not used)
• T2': symbol to write to scratch tape #1
• T3': symbol to write to scratch tape #2
• T4': symbol to write to output tape
• D1: direction to move input tape head
• D2: direction to move scratch tape #1 head
• D3: direction to move scratch tape #2 head
• D4: direction to move output tape head

Conventions:

• w, x, y and z are variables and represent either 0 or 1. A transition using all four of these can be thought of as a shorthand notation for writing sixteen (2^4) concrete transitions.
• directions are L=left, S=same, R=right.
• B is a blank symbol; it can be dispensed with if you add more states to assist U and V in the addition.