i
The Thumb Is the State daniel-hromada ()


The Thumb Is the State

Look again at the rule table of our Turing machine — the one from the Alan session — and write the state as a bit: CARRY = 1, HALT = 0.

state creads bwritesnext statemove
1 (CARRY)010 (HALT)left
1 (CARRY)101 (CARRY)left
0 (HALT)000—
0 (HALT)110—

Writes = b XOR c. Next state = b AND c. The rule table of the machine is the half-adder’s truth table.

A Turing machine is a half-adder with a memory and a moving head. The carry is the thumb of the other hand.