// b_add.tm binary addition given 1010+0011= form of input // compute the sum =1101 // // The basic algorithm is to compute a+b=s bit by bit starting // with a carry-in of zero and computing the sum bit and next // carry bit. The standard binary addition truth table is // converted to a state diagram and coded as Turing Machine // transitions: // // a b c_in s c_out state name for each case // // 0 0 0 0 0 c0b0a0 // 0 0 1 1 0 c0b0a1 // 0 1 0 1 0 c0b1a0 // 0 1 1 0 1 c0b1a1 // 1 0 0 1 0 c1b0a0 // 1 0 1 0 1 c1b0a1 // 1 1 0 0 1 c1b1a0 // 1 1 1 1 1 c1b1a1 start s halt f s 0 s ## R move right to find "=" s 1 s ## R s + s ## R s = c0 ## L found "=", go to state c0 c0 #b c0 ## L c_in is zero, go to state for "b" bit c0 0 c0b0 #b L lsb "b" is zero c0 1 c0b1 #b L lsb "b" is one c0 + c0b0t ## L c0b0 #b c0b0 ## L c_in is zero, b is zero, move left to find "a" c0b0 0 c0b0 ## L c0b0 1 c0b0 ## L c0b0 + c0b0t ## L c0b0 #[ c0b0a0 ## R hit front of tape, "a" is default zero c0b0t #b c0b0t ## L move left to blank, then back to find lsb of "a" c0b0t 1 c0b0a1 #b R lsb "a" is one, blank it out, done with this bit c0b0t 0 c0b0a0 #b R lsb "a" is zero, blank it out, done with this bit c0b0t #[ c0b0a0 ## R hit front of tape, "a" is default zero c0b0a0 + c0b0a0p ## R c0b0a0p = c0b0a0q ## L special test for done c0b0a0q + f #b N c0b0a0p 0 c0b0a0n ## R c0b0a0p 1 c0b0a0n ## R c0b0a0p #b c0b0a0n ## R c0b0a0 1 c0b0a0n ## R c0b0a0 0 c0b0a0n ## R c0b0a0 #b c0b0a0n ## R c0b0a0n 1 c0b0a0n ## R c0b0a0n 0 c0b0a0n ## R c0b0a0n #b c0b0a0n ## R c0b0a0n + c0b0a0n ## R c0b0a0n = c0b0a0w 0 L write sum bit c0b0a0 = c0b0a0w 0 L write sum bit c0b0a0w #b c0 = L re write = c0b0a0w + c0b0a0x = L re write = and + c0b0a0x #b c0b0t + L re write + c0b0a1 + c0b0a1 ## R c0b0a1 1 c0b0a1 ## R c0b0a1 0 c0b0a1 ## R c0b0a1 #b c0b0a1 ## R c0b0a1 = c0b0a1w 1 L write sum bit c0b0a1w #b c0 = L re write = c0b0a1w + c0b0a1x = L re write = and + c0b0a1x #b c0b0t + L re write + c0b1 #b c0b1 ## L c0b1 0 c0b1 ## L c0b1 1 c0b1 ## L c0b1 + c0b1t ## L c0b1 #[ c0b1a0 ## R c0b1t #b c0b1t ## L c is zero, b is one, find lsb of "a" c0b1t 1 c0b1a1 #b R c0b1t 0 c0b1a0 #b R c0b1t #[ c0b1a0 ## R c0b1a0 + c0b1a0 ## R c0b1a0 1 c0b1a0 ## R c0b1a0 0 c0b1a0 ## R c0b1a0 #b c0b1a0 ## R c0b1a0 = c0b1a0w 1 L write sum bit c0b1a0w #b c0 = L re write = c0b1a0w + c0b1a0x = L re write = and + c0b1a0x #b c0b1t + L re write + c0b1a1 + c0b1a1 ## R c0b1a1 1 c0b1a1 ## R c0b1a1 0 c0b1a1 ## R c0b1a1 #b c0b1a1 ## R c0b1a1 = c0b1a1w 0 L write sum bit c0b1a1w #b c1 = L re write = c0b1a1w + c0b1a1x = L re write = and + c0b1a1x #b c1b0t + L re write + c1 #b c1 ## L c is one, find lsb of "b" c1 0 c1b0 #b L c1 1 c1b1 #b L c1 + c1b0t ## L c1b0 #b c1b0 ## L c1b0 0 c1b0 ## L c1b0 1 c1b0 ## L c1b0 + c1b0t ## L c1b0 #[ c1b0a0 ## R c1b0t #b c1b0t ## L c is one, b is zero, find lsb of "a" c1b0t 1 c1b0a1 #b R c1b0t 0 c1b0a0 #b R c1b0t #[ c1b0a0 ## R c1b0a0 + c1b0a0 ## R c1b0a0 1 c1b0a0 ## R c1b0a0 0 c1b0a0 ## R c1b0a0 #b c1b0a0 ## R c1b0a0 = c1b0a0w 1 L write sum bit c1b0a0w #b c0 = L re write = c1b0a0w + c1b0a0x = L re write = and + c1b0a0x #b c0b0t + L re write + c1b0a1 + c1b0a1 ## R c1b0a1 1 c1b0a1 ## R c1b0a1 0 c1b0a1 ## R c1b0a1 #b c1b0a1 ## R c1b0a1 = c1b0a1w 0 L write sum bit c1b0a1w #b c1 = L re write = c1b0a1w + c1b0a1x = L re write = and + c1b0a1x #b c1b0t + L re write + c1b1 #b c1b1 ## L back up to "+" c1b1 0 c1b1 ## L c1b1 1 c1b1 ## L c1b1 + c1b1t ## L c1b1 #[ c1b1a0 ## R c1b1t #b c1b1t ## L c is one, b is one, find lsb of "a" c1b1t 1 c1b1a1 #b R c1b1t 0 c1b1a0 #b R c1b1t #[ c1b1a0 ## R c1b1a0 + c1b1a0 ## R c1b1a0 1 c1b1a0 ## R c1b1a0 0 c1b1a0 ## R c1b1a0 #b c1b1a0 ## R c1b1a0 = c1b1a0w 0 L write sum bit c1b1a0w #b c1 = L re write = c1b1a0w + c1b1a0x = L re write = and + c1b1a0x #b c1b0t + L re write + c1b1a1 + c1b1a1 ## R c1b1a1 1 c1b1a1 ## R c1b1a1 0 c1b1a1 ## R c1b1a1 #b c1b1a1 ## R c1b1a1 = c1b1a1w 1 L write sum bit c1b1a1w #b c1 = L re write = c1b1a1w + c1b1a1x = L re write = and + c1b1a1x #b c1b0t + L re write + enddef test cases follow tape 00+00= tape 01+00= tape 10+00= tape 11+00= tape 00+01= tape 01+01= tape 10+01= tape 11+01= tape 00+10= tape 01+10= tape 10+10= tape 11+10= tape 00+11= tape 01+11= tape 10+11= tape 11+11= tape 010+101= tape 0101+0011= tape 1+1111= tape 1111+1= tape 0+0000= tape 0000+0= tape 0+1111= tape 1111+0=