# a Virtual Turing Machine that multiplies two integers. # # The number N is represented by (n+1) consecutive 1's, # so "zero" is _1_, "one" is _11_, and so on. # (This lets us represent zero as _1_ .) # # At the start of the calculation, the tape holds the two numbers # with a blank character between 'em, and the head is just to the # at the leftmost 1 of the first number. # e.g. "two times three" is "_<1>1 1 _ 1 1 1 1 _" . # # At the end of the calculation, the tape holds the product, # e.g. "six" is _1111111_, and the head is at the leftmost 1. # # The procedure below works like this, # illustrated on "two times three". _ 1 1 1 _ 1 1 1 1 # # I) Mark the numbers and their start/end, # and remove a 1 for each number _ a 1 1 b 2 2 2 c # II) For each 1, # 1) replace it with _, then # 2) for each 2, # i) replace it with Z, # ii) copy it past c _ a _ 1 b Z 2 2 c 1 _ # _ a _ 1 b Z Z 2 c 1 1 _ # 3) turn Z's back to 2's _ a _ 1 b 2 2 2 c 1 1 1 _ # _ a _ _ b 2 2 2 c 1 1 1 1 1 1 _ # III) Clean up by setting # 'a' and 'b' to _, and 'c' to 1. _ _ _ _ _ _ _ _ 1 1 1 1 1 1 1 _ # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # _<1>1 1 _ 1 1 1 1 : start start: "start" tape: "*" blank: "_" accept: [] reject: [] machine: # _<1>1 1 _ 1 1 1 1 : start - [ start, 1, setB, a, right] - [ setB, 1, setB, 1, right] - [ setB, _, find_, b, right] - [ find_, 1, find_, 2, right] - [ find_, _, setC, _, left] - [ setC, 2, nextA, c, left] # _ a 1 1 b 2 2<2>c _ : nextA - [ nextA, 2, nextA, 2, left] - [ nextA, 1, nextA, 1, left] - [ nextA, b, nextA, b, left] - [ nextA, _, nextA, _, left] - [ nextA, a, digit, a, right] # - [ digit, _, digit, _, right] - [ digit, b, eraseA, _, left] - [ digit, 1, copy, _, right] # _ a _<1>b 2 2 2 c _ : copy - [ copy, 1, copy, 1, right] - [ copy, b, copy, b, right] - [ copy, 2, copyright, Z, right] - [ copy, c, nextA, c, left] - [ copyright, 2, copyright, 2, right] - [ copyright, Z, copyright, Z, right] - [ copyright, c, copyright, c, right] - [ copyright, 1, copyright, 1, right] - [ copyright, _, copyleft, 1, left] - [ copyleft, 1, copyleft, 1, left] - [ copyleft, c, copyleft, c, left] - [ copyleft, 2, copyright, Z, right] - [ copyleft, Z, copyleft, Z, left] - [ copyleft, b, Zto2, b, right] # _ a _ 1 bZ Z c 1 1 1 : Zto2 - [ Zto2, Z, Zto2, 2, right] - [ Zto2, c, nextA, c, left] # _ a _<_>_ 2 2 2 c 1 1 1 1 1 1 : eraseA - [ eraseA, _, eraseA, _, left] - [ eraseA, a, clean, _, right] - [ clean, 2, clean, _, right] - [ clean, _, clean, _, right] - [ clean, c, penul, 1, left] - [ penul, _, halt, _, right] # _ _ _ _ _ _ _ _<1>1 1 1 1 1 1 : halt # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # Examples # 2*3=6 # Specify initial tape: 111_1111 # 0: <1>1 1 _ 1 1 1 1 : start # 0: a<1>1 _ 1 1 1 1 : setB # 0: a 1<1>_ 1 1 1 1 : setB # 0: a 1 1<_>1 1 1 1 : setB # 0: a 1 1 b<1>1 1 1 : find_ # 0: a 1 1 b 2<1>1 1 : find_ # 0: a 1 1 b 2 2<1>1 : find_ # 0: a 1 1 b 2 2 2<1>: find_ # 0: a 1 1 b 2 2 2 2<_>: find_ # 0: a 1 1 b 2 2 2<2>_ : setC # 0: a 1 1 b 2 2<2>c _ : nextA # 0: a 1 1 b 2<2>2 c _ : nextA # 0: a 1 1 b<2>2 2 c _ : nextA # 0: a 1 12 2 2 c _ : nextA # 0: a 1<1>b 2 2 2 c _ : nextA # 0: a<1>1 b 2 2 2 c _ : nextA # 0: 1 1 b 2 2 2 c _ : nextA # 0: a<1>1 b 2 2 2 c _ : digit # 0: a _<1>b 2 2 2 c _ : copy # 0: a _ 12 2 2 c _ : copy # 0: a _ 1 b<2>2 2 c _ : copy # 0: a _ 1 b Z<2>2 c _ : copyR # 0: a _ 1 b Z 2<2>c _ : copyR # 0: a _ 1 b Z 2 2_ : copyR # 0: a _ 1 b Z 2 2 c<_>: copyR # 0: a _ 1 b Z 2 21 : copyL # 0: a _ 1 b Z 2<2>c 1 : copyL # 0: a _ 1 b Z 2 Z1 : copyR # 0: a _ 1 b Z 2 Z c<1>: copyR # 0: a _ 1 b Z 2 Z c 1<_>: copyR # 0: a _ 1 b Z 2 Z c<1>1 : copyL # 0: a _ 1 b Z 2 Z1 1 : copyL # 0: a _ 1 b Z 2c 1 1 : copyL # 0: a _ 1 b Z<2>Z c 1 1 : copyL # 0: a _ 1 b Z Zc 1 1 : copyR # 0: a _ 1 b Z Z Z1 1 : copyR # 0: a _ 1 b Z Z Z c<1>1 : copyR # 0: a _ 1 b Z Z Z c 1<1>: copyR # 0: a _ 1 b Z Z Z c 1 1<_>: copyR # 0: a _ 1 b Z Z Z c 1<1>1 : copyL # 0: a _ 1 b Z Z Z c<1>1 1 : copyL # 0: a _ 1 b Z Z Z1 1 1 : copyL # 0: a _ 1 b Z Zc 1 1 1 : copyL # 0: a _ 1 b ZZ c 1 1 1 : copyL # 0: a _ 1 bZ Z c 1 1 1 : copyL # 0: a _ 1Z Z Z c 1 1 1 : copyL # 0: a _ 1 bZ Z c 1 1 1 : Zto2 # 0: a _ 1 b 2Z c 1 1 1 : Zto2 # 0: a _ 1 b 2 2c 1 1 1 : Zto2 # 0: a _ 1 b 2 2 21 1 1 : Zto2 # 0: a _ 1 b 2 2<2>c 1 1 1 : nextA # 0: a _ 1 b 2<2>2 c 1 1 1 : nextA # 0: a _ 1 b<2>2 2 c 1 1 1 : nextA # 0: a _ 12 2 2 c 1 1 1 : nextA # 0: a _<1>b 2 2 2 c 1 1 1 : nextA # 0: a<_>1 b 2 2 2 c 1 1 1 : nextA # 0: _ 1 b 2 2 2 c 1 1 1 : nextA # 0: a<_>1 b 2 2 2 c 1 1 1 : digit # 0: a _<1>b 2 2 2 c 1 1 1 : digit # 0: a _ _2 2 2 c 1 1 1 : copy # 0: a _ _ b<2>2 2 c 1 1 1 : copy # 0: a _ _ b Z<2>2 c 1 1 1 : copyR # 0: a _ _ b Z 2<2>c 1 1 1 : copyR # 0: a _ _ b Z 2 21 1 1 : copyR # 0: a _ _ b Z 2 2 c<1>1 1 : copyR # 0: a _ _ b Z 2 2 c 1<1>1 : copyR # 0: a _ _ b Z 2 2 c 1 1<1>: copyR # 0: a _ _ b Z 2 2 c 1 1 1<_>: copyR # 0: a _ _ b Z 2 2 c 1 1<1>1 : copyL # 0: a _ _ b Z 2 2 c 1<1>1 1 : copyL # 0: a _ _ b Z 2 2 c<1>1 1 1 : copyL # 0: a _ _ b Z 2 21 1 1 1 : copyL # 0: a _ _ b Z 2<2>c 1 1 1 1 : copyL # 0: a _ _ b Z 2 Z1 1 1 1 : copyR # 0: a _ _ b Z 2 Z c<1>1 1 1 : copyR # 0: a _ _ b Z 2 Z c 1<1>1 1 : copyR # 0: a _ _ b Z 2 Z c 1 1<1>1 : copyR # 0: a _ _ b Z 2 Z c 1 1 1<1>: copyR # 0: a _ _ b Z 2 Z c 1 1 1 1<_>: copyR # 0: a _ _ b Z 2 Z c 1 1 1<1>1 : copyL # 0: a _ _ b Z 2 Z c 1 1<1>1 1 : copyL # 0: a _ _ b Z 2 Z c 1<1>1 1 1 : copyL # 0: a _ _ b Z 2 Z c<1>1 1 1 1 : copyL # 0: a _ _ b Z 2 Z1 1 1 1 1 : copyL # 0: a _ _ b Z 2c 1 1 1 1 1 : copyL # 0: a _ _ b Z<2>Z c 1 1 1 1 1 : copyL # 0: a _ _ b Z Zc 1 1 1 1 1 : copyR # 0: a _ _ b Z Z Z1 1 1 1 1 : copyR # 0: a _ _ b Z Z Z c<1>1 1 1 1 : copyR # 0: a _ _ b Z Z Z c 1<1>1 1 1 : copyR # 0: a _ _ b Z Z Z c 1 1<1>1 1 : copyR # 0: a _ _ b Z Z Z c 1 1 1<1>1 : copyR # 0: a _ _ b Z Z Z c 1 1 1 1<1>: copyR # 0: a _ _ b Z Z Z c 1 1 1 1 1<_>: copyR # 0: a _ _ b Z Z Z c 1 1 1 1<1>1 : copyL # 0: a _ _ b Z Z Z c 1 1 1<1>1 1 : copyL # 0: a _ _ b Z Z Z c 1 1<1>1 1 1 : copyL # 0: a _ _ b Z Z Z c 1<1>1 1 1 1 : copyL # 0: a _ _ b Z Z Z c<1>1 1 1 1 1 : copyL # 0: a _ _ b Z Z Z1 1 1 1 1 1 : copyL # 0: a _ _ b Z Zc 1 1 1 1 1 1 : copyL # 0: a _ _ b ZZ c 1 1 1 1 1 1 : copyL # 0: a _ _ bZ Z c 1 1 1 1 1 1 : copyL # 0: a _ _Z Z Z c 1 1 1 1 1 1 : copyL # 0: a _ _ bZ Z c 1 1 1 1 1 1 : Zto2 # 0: a _ _ b 2Z c 1 1 1 1 1 1 : Zto2 # 0: a _ _ b 2 2c 1 1 1 1 1 1 : Zto2 # 0: a _ _ b 2 2 21 1 1 1 1 1 : Zto2 # 0: a _ _ b 2 2<2>c 1 1 1 1 1 1 : nextA # 0: a _ _ b 2<2>2 c 1 1 1 1 1 1 : nextA # 0: a _ _ b<2>2 2 c 1 1 1 1 1 1 : nextA # 0: a _ _2 2 2 c 1 1 1 1 1 1 : nextA # 0: a _<_>b 2 2 2 c 1 1 1 1 1 1 : nextA # 0: a<_>_ b 2 2 2 c 1 1 1 1 1 1 : nextA # 0: _ _ b 2 2 2 c 1 1 1 1 1 1 : nextA # 0: a<_>_ b 2 2 2 c 1 1 1 1 1 1 : digit # 0: a _<_>b 2 2 2 c 1 1 1 1 1 1 : digit # 0: a _ _2 2 2 c 1 1 1 1 1 1 : digit # 0: a _<_>_ 2 2 2 c 1 1 1 1 1 1 : eraseA # 0: a<_>_ _ 2 2 2 c 1 1 1 1 1 1 : eraseA # 0: _ _ _ 2 2 2 c 1 1 1 1 1 1 : eraseA # 0: _<_>_ _ 2 2 2 c 1 1 1 1 1 1 : clean # 0: _ _<_>_ 2 2 2 c 1 1 1 1 1 1 : clean # 0: _ _ _<_>2 2 2 c 1 1 1 1 1 1 : clean # 0: _ _ _ _<2>2 2 c 1 1 1 1 1 1 : clean # 0: _ _ _ _ _<2>2 c 1 1 1 1 1 1 : clean # 0: _ _ _ _ _ _<2>c 1 1 1 1 1 1 : clean # 0: _ _ _ _ _ _ _1 1 1 1 1 1 : clean # 0: _ _ _ _ _ _<_>1 1 1 1 1 1 1 : penul # 0: _ _ _ _ _ _ _<1>1 1 1 1 1 1 : halt # 0*2=0 # Specify initial tape: 1_111 # 0: <1>_ 1 1 1 : start # 0: a<_>1 1 1 : setB # 0: a b<1>1 1 : find_ # 0: a b 2<1>1 : find_ # 0: a b 2 2<1>: find_ # 0: a b 2 2 2<_>: find_ # 0: a b 2 2<2>_ : setC # 0: a b 2<2>c _ : nextA # 0: a b<2>2 c _ : nextA # 0: a2 2 c _ : nextA # 0: b 2 2 c _ : nextA # 0: a2 2 c _ : digit # 0: _ 2 2 c _ : eraseA # 0: _<_>2 2 c _ : clean # 0: _ _<2>2 c _ : clean # 0: _ _ _<2>c _ : clean # 0: _ _ _ __ : clean # 0: _ _ _<_>1 _ : penul # 0: _ _ _ _<1>_ : halt # 2*0=0 # Specify initial tape: 1_111 # 0: <1>_ 1 1 1 : start # 0: a<_>1 1 1 : setB # 0: a b<1>1 1 : find_ # 0: a b 2<1>1 : find_ # 0: a b 2 2<1>: find_ # 0: a b 2 2 2<_>: find_ # 0: a b 2 2<2>_ : setC # 0: a b 2<2>c _ : nextA # 0: a b<2>2 c _ : nextA # 0: a2 2 c _ : nextA # 0: b 2 2 c _ : nextA # 0: a2 2 c _ : digit # 0: _ 2 2 c _ : eraseA # 0: _<_>2 2 c _ : clean # 0: _ _<2>2 c _ : clean # 0: _ _ _<2>c _ : clean # 0: _ _ _ __ : clean # 0: _ _ _<_>1 _ : penul # 0: _ _ _ _<1>_ : halt # 1*3=3 # Specify initial tape: 11_1111 # 0: <1>1 _ 1 1 1 1 : start # 0: a<1>_ 1 1 1 1 : setB # 0: a 1<_>1 1 1 1 : setB # 0: a 1 b<1>1 1 1 : find_ # 0: a 1 b 2<1>1 1 : find_ # 0: a 1 b 2 2<1>1 : find_ # 0: a 1 b 2 2 2<1>: find_ # 0: a 1 b 2 2 2 2<_>: find_ # 0: a 1 b 2 2 2<2>_ : setC # 0: a 1 b 2 2<2>c _ : nextA # 0: a 1 b 2<2>2 c _ : nextA # 0: a 1 b<2>2 2 c _ : nextA # 0: a 12 2 2 c _ : nextA # 0: a<1>b 2 2 2 c _ : nextA # 0: 1 b 2 2 2 c _ : nextA # 0: a<1>b 2 2 2 c _ : digit # 0: a _2 2 2 c _ : copy # 0: a _ b<2>2 2 c _ : copy # 0: a _ b Z<2>2 c _ : copyR # 0: a _ b Z 2<2>c _ : copyR # 0: a _ b Z 2 2_ : copyR # 0: a _ b Z 2 2 c<_>: copyR # 0: a _ b Z 2 21 : copyL # 0: a _ b Z 2<2>c 1 : copyL # 0: a _ b Z 2 Z1 : copyR # 0: a _ b Z 2 Z c<1>: copyR # 0: a _ b Z 2 Z c 1<_>: copyR # 0: a _ b Z 2 Z c<1>1 : copyL # 0: a _ b Z 2 Z1 1 : copyL # 0: a _ b Z 2c 1 1 : copyL # 0: a _ b Z<2>Z c 1 1 : copyL # 0: a _ b Z Zc 1 1 : copyR # 0: a _ b Z Z Z1 1 : copyR # 0: a _ b Z Z Z c<1>1 : copyR # 0: a _ b Z Z Z c 1<1>: copyR # 0: a _ b Z Z Z c 1 1<_>: copyR # 0: a _ b Z Z Z c 1<1>1 : copyL # 0: a _ b Z Z Z c<1>1 1 : copyL # 0: a _ b Z Z Z1 1 1 : copyL # 0: a _ b Z Zc 1 1 1 : copyL # 0: a _ b ZZ c 1 1 1 : copyL # 0: a _ bZ Z c 1 1 1 : copyL # 0: a _Z Z Z c 1 1 1 : copyL # 0: a _ bZ Z c 1 1 1 : Zto2 # 0: a _ b 2Z c 1 1 1 : Zto2 # 0: a _ b 2 2c 1 1 1 : Zto2 # 0: a _ b 2 2 21 1 1 : Zto2 # 0: a _ b 2 2<2>c 1 1 1 : nextA # 0: a _ b 2<2>2 c 1 1 1 : nextA # 0: a _ b<2>2 2 c 1 1 1 : nextA # 0: a _2 2 2 c 1 1 1 : nextA # 0: a<_>b 2 2 2 c 1 1 1 : nextA # 0: _ b 2 2 2 c 1 1 1 : nextA # 0: a<_>b 2 2 2 c 1 1 1 : digit # 0: a _2 2 2 c 1 1 1 : digit # 0: a<_>_ 2 2 2 c 1 1 1 : eraseA # 0: _ _ 2 2 2 c 1 1 1 : eraseA # 0: _<_>_ 2 2 2 c 1 1 1 : clean # 0: _ _<_>2 2 2 c 1 1 1 : clean # 0: _ _ _<2>2 2 c 1 1 1 : clean # 0: _ _ _ _<2>2 c 1 1 1 : clean # 0: _ _ _ _ _<2>c 1 1 1 : clean # 0: _ _ _ _ _ _1 1 1 : clean # 0: _ _ _ _ _<_>1 1 1 1 : penul # 0: _ _ _ _ _ _<1>1 1 1 : halt # 3*1=3 # Specify initial tape: 1111_11 # 0: <1>1 1 1 _ 1 1 : start # 0: a<1>1 1 _ 1 1 : setB # 0: a 1<1>1 _ 1 1 : setB # 0: a 1 1<1>_ 1 1 : setB # 0: a 1 1 1<_>1 1 : setB # 0: a 1 1 1 b<1>1 : find_ # 0: a 1 1 1 b 2<1>: find_ # 0: a 1 1 1 b 2 2<_>: find_ # 0: a 1 1 1 b 2<2>_ : setC # 0: a 1 1 1 b<2>c _ : nextA # 0: a 1 1 12 c _ : nextA # 0: a 1 1<1>b 2 c _ : nextA # 0: a 1<1>1 b 2 c _ : nextA # 0: a<1>1 1 b 2 c _ : nextA # 0: 1 1 1 b 2 c _ : nextA # 0: a<1>1 1 b 2 c _ : digit # 0: a _<1>1 b 2 c _ : copy # 0: a _ 1<1>b 2 c _ : copy # 0: a _ 1 12 c _ : copy # 0: a _ 1 1 b<2>c _ : copy # 0: a _ 1 1 b Z_ : copyR # 0: a _ 1 1 b Z c<_>: copyR # 0: a _ 1 1 b Z1 : copyL # 0: a _ 1 1 bc 1 : copyL # 0: a _ 1 1Z c 1 : copyL # 0: a _ 1 1 bc 1 : Zto2 # 0: a _ 1 1 b 21 : Zto2 # 0: a _ 1 1 b<2>c 1 : nextA # 0: a _ 1 12 c 1 : nextA # 0: a _ 1<1>b 2 c 1 : nextA # 0: a _<1>1 b 2 c 1 : nextA # 0: a<_>1 1 b 2 c 1 : nextA # 0: _ 1 1 b 2 c 1 : nextA # 0: a<_>1 1 b 2 c 1 : digit # 0: a _<1>1 b 2 c 1 : digit # 0: a _ _<1>b 2 c 1 : copy # 0: a _ _ 12 c 1 : copy # 0: a _ _ 1 b<2>c 1 : copy # 0: a _ _ 1 b Z1 : copyR # 0: a _ _ 1 b Z c<1>: copyR # 0: a _ _ 1 b Z c 1<_>: copyR # 0: a _ _ 1 b Z c<1>1 : copyL # 0: a _ _ 1 b Z1 1 : copyL # 0: a _ _ 1 bc 1 1 : copyL # 0: a _ _ 1Z c 1 1 : copyL # 0: a _ _ 1 bc 1 1 : Zto2 # 0: a _ _ 1 b 21 1 : Zto2 # 0: a _ _ 1 b<2>c 1 1 : nextA # 0: a _ _ 12 c 1 1 : nextA # 0: a _ _<1>b 2 c 1 1 : nextA # 0: a _<_>1 b 2 c 1 1 : nextA # 0: a<_>_ 1 b 2 c 1 1 : nextA # 0: _ _ 1 b 2 c 1 1 : nextA # 0: a<_>_ 1 b 2 c 1 1 : digit # 0: a _<_>1 b 2 c 1 1 : digit # 0: a _ _<1>b 2 c 1 1 : digit # 0: a _ _ _2 c 1 1 : copy # 0: a _ _ _ b<2>c 1 1 : copy # 0: a _ _ _ b Z1 1 : copyR # 0: a _ _ _ b Z c<1>1 : copyR # 0: a _ _ _ b Z c 1<1>: copyR # 0: a _ _ _ b Z c 1 1<_>: copyR # 0: a _ _ _ b Z c 1<1>1 : copyL # 0: a _ _ _ b Z c<1>1 1 : copyL # 0: a _ _ _ b Z1 1 1 : copyL # 0: a _ _ _ bc 1 1 1 : copyL # 0: a _ _ _Z c 1 1 1 : copyL # 0: a _ _ _ bc 1 1 1 : Zto2 # 0: a _ _ _ b 21 1 1 : Zto2 # 0: a _ _ _ b<2>c 1 1 1 : nextA # 0: a _ _ _2 c 1 1 1 : nextA # 0: a _ _<_>b 2 c 1 1 1 : nextA # 0: a _<_>_ b 2 c 1 1 1 : nextA # 0: a<_>_ _ b 2 c 1 1 1 : nextA # 0: _ _ _ b 2 c 1 1 1 : nextA # 0: a<_>_ _ b 2 c 1 1 1 : digit # 0: a _<_>_ b 2 c 1 1 1 : digit # 0: a _ _<_>b 2 c 1 1 1 : digit # 0: a _ _ _2 c 1 1 1 : digit # 0: a _ _<_>_ 2 c 1 1 1 : eraseA # 0: a _<_>_ _ 2 c 1 1 1 : eraseA # 0: a<_>_ _ _ 2 c 1 1 1 : eraseA # 0: _ _ _ _ 2 c 1 1 1 : eraseA # 0: _<_>_ _ _ 2 c 1 1 1 : clean # 0: _ _<_>_ _ 2 c 1 1 1 : clean # 0: _ _ _<_>_ 2 c 1 1 1 : clean # 0: _ _ _ _<_>2 c 1 1 1 : clean # 0: _ _ _ _ _<2>c 1 1 1 : clean # 0: _ _ _ _ _ _1 1 1 : clean # 0: _ _ _ _ _<_>1 1 1 1 : penul # 0: _ _ _ _ _ _<1>1 1 1 : halt