turing-machine/examples/binary_multiplication at master · dieggsy/turing-machine · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
; -*- mode: turing-machine -*-
; http://morphett.info/turing/turing.html
; Binary multiplication machine - multiplies two numbers given in binary
; Input: two numbers in binary, separated by a space, eg "101 1101"
; Output: the product of the two inputs, in binary

; The machine stores data on the tape in the configuration "tally num1 num2" where num1, num2 are the input and tally is the running total for the product.

; Set up tally
0 * * l 1
1 _ _ l 2
2 _ 0 r 3
3 _ _ r 10

; Find end of num1
10 _ _ l 11
10 x x l 11
10 0 0 r 10
10 1 1 r 10


; If last digit of num1 is 0, multiply num2 by 2
11 0 x r 20
; If last digit of num1 is 1, add num2 to tally and then multiply num2 by 2
11 1 x r 30


; Multiply num2 by 2
20 _ _ r 20
20 x x r 20
20 * * r 21
21 _ 0 l 25 ; Multiplication by 2 done, return to end of num1
21 * * r 21
25 _ _ l 26
25 * * l 25
26 _ _ r 80 ; Finished multiplying. Clean up
26 x x l 26
26 0 0 * 11
26 1 1 * 11

; Add num2 to tally
30 _ _ r 30
30 x x r 30
30 * * r 31
31 _ _ l 32
31 * * r 31
32 0 o l 40 ; Add a zero
32 1 i l 50 ; Add a one
32 o o l 32
32 i i l 32
32 _ _ r 70 ; Finished adding

; Adding a 0 to tally
40 _ _ l 41
40 * * l 40 ; Found end of num2
41 _ _ l 41
41 * * l 42 ; Found start of num1
42 _ _ l 43 ; Found end of num1
42 * * l 42
43 o o l 43
43 i i l 43
43 0 o r 44
43 1 i r 44
43 _ o r 44
44 _ _ r 45 ; Found end of tally
44 * * r 44
45 _ _ r 45
45 * * r 46 ; Found start of num1
46 _ _ r 47 ; Found end of num1
46 * * r 46
47 _ _ r 47
47 * * r 48
48 _ _ l 32 ; Found end of num2
48 * * r 48

; Adding a 1 to tally
50 _ _ l 51 ; Found end of num2
50 * * l 50
51 _ _ l 51
51 * * l 52 ; Found start of num1
52 _ _ l 53 ; Found end of num1
52 * * l 52
53 o o l 53
53 i i l 53
53 _ i r 55
53 0 i r 55 ; return to num2
53 1 o l 54
54 0 1 r 55
54 1 0 l 54
54 _ 1 r 55
55 _ _ r 56 ; Found end of tally
55 * * r 55
56 _ _ r 56
56 * * r 57 ; Found start of num1
57 _ _ r 58 ; Found end of num1
57 * * r 57
58 _ _ r 58
58 * * r 59
59 _ _ l 32 ; Found end of num2
59 * * r 59

; Finished adding, clean up
70 i 1 r 70
70 o 0 r 70
70 _ _ l 71
71 _ _ l 72 ; Found end of num2
71 * * l 71
72 _ _ l 72
72 * * l 73 ; Found start of num1
73 _ _ l 74
73 * * l 73
74 o 0 l 74
74 i 1 l 74
74 * * r 75 ; Finished cleaning up tally
75 _ _ r 76
75 * * r 75
76 _ _ r 20 ; Multiply num2 by 2
76 * * r 76

; Finished multiplying, clean up
80 x _ r 80
80 _ _ r 81
81 _ _ l 82
81 * _ r 81
82 _ _ l 82
82 * * * halt