Program Examples
Turing Machine Doing Subtraction
Although there are a number of Turing state machines that will accomplish subtraction, this method uses only ones, zeros, and blank cells. It's not that difficult to understand how a Turing machine does subtraction.
In this example, the space between the number sets separates the two sides of the equation. The machine removes matching "1"s from each side of the equation until there are no more "1"s on the right side. A count of the "1"s on the left side of the equation gives us the answer.
While there are a large number of states in this example, most of them are responsible for finding the parts of the equation and the ends of each part (states 0, 1, 3, 4, 5). Two states (states 6 and 7) remove the leftover zeros at the end. The two states "2" and "8" remove the ones that match on each side of the equation.
The States Used For This Example (Explanation of the Programming Syntax Used)
(0,0) -> (0,0) Right //finds right edge of first number (0,1) -> (0,1) Right (0,B) -> (1,B) Right (1,0) -> (1,0) Right //finds right edge of second number (1,1) -> (1,1) Right (1,B) -> (2,B) Left (2,0) -> (2,0) Left //if a 0 keep looking for a 1 (2,1) -> (3,0) Left //removed right most 1 from right number (2,B) -> (5,B) Right //if we find a blank before a 1, then erase 0s (3,0) -> (3,0) Left //move to left number (3,1) -> (3,1) Left (3,B) -> (8,B) Left (4,0) -> (4,0) Right //finds right edge of first number (4,1) -> (4,1) Right (4,B) -> (5,B) Right (5,0) -> (5,0) Right //finds right edge of second number (5,1) -> (5,1) Right (5,B) -> (6,B) Left (6,0) -> (6,B) Left //removed 0 from right number (6,1) -> (6,1) Left (6,B) -> (7,B) Left (7,0) -> (7, ) Left //removes 0 from left number (7,1) -> (7,1) Left (7,B) -> (9,B) Right (8,0) -> (8,0) Left //move left looking for a 1 to change to a 0 (8,1) -> (0,0) Right //if a 1 is found, change to zero and loop again (8,B) -> (4,B) Right //if blank then all done, then erase 0s (9,0) -> (9,0) Halt //halts the program (9,1) -> (9,1) Halt (9,B) -> (9,0) Halt