#!/usr/bin/env vtm -L -S -sstart -b_ ##echo This is a Virtual Turing Machine that multiplies two integers. ##echo ##echo The number N is represented by (n+1) consecutive 1's, ##echo so "zero" is _1_, "one" is _11_, and so on. ##echo (This lets us represent zero as _1_ .) ##echo ##echo At the start of the calculation, the tape holds the two numbers ##echo with a blank character between 'em, and the head is just to the ##echo at the leftmost 1 of the first number. ##echo e.g. "two times three" is "_<1>1 1 _ 1 1 1 1 _" . ##echo ##echo At the end of the calculation, the tape holds the product, ##echo e.g. "six" is _1111111_, and the head is at the leftmost 1. ##echo # -L : turn on echo # -sstart : start in state 'start' # -t* : start with tape * (or prompt if not specified above). # -b_ : blank char is '_' # -S : show state at line end # 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, 1, setB, a, R setB, 1, setB, 1, R setB, _, find_, b, R find_, 1, find_, 2, R find_, _, setC, _, L setC, 2, nextA, c, L # _ a 1 1 b 2 2<2>c _ : nextA nextA, 2, nextA, 2, L nextA, 1, nextA, 1, L nextA, b, nextA, b, L nextA, _, nextA, _, L nextA, a, digit, a, R # digit, _, digit, _, R digit, b, eraseA, _, L digit, 1, copy, _, R # _ a _<1>b 2 2 2 c _ : copy copy, 1, copy, 1, R copy, b, copy, b, R copy, 2, copyR, Z, R copy, c, nextA, c, L copyR, 2, copyR, 2, R copyR, Z, copyR, Z, R copyR, c, copyR, c, R copyR, 1, copyR, 1, R copyR, _, copyL, 1, L copyL, 1, copyL, 1, L copyL, c, copyL, c, L copyL, 2, copyR, Z, R copyL, Z, copyL, Z, L copyL, b, Zto2, b, R # _ a _ 1 bZ Z c 1 1 1 : Zto2 Zto2, Z, Zto2, 2, R Zto2, c, nextA, c, L # _ a _<_>_ 2 2 2 c 1 1 1 1 1 1 : eraseA eraseA, _, eraseA, _, L eraseA, a, clean, _, R clean, 2, clean, _, R clean, _, clean, _, R clean, c, penul, 1, L penul, _, halt, _, R # _ _ _ _ _ _ _ _<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