report.md (5987B)
1 [toc] 2 3 # Turing Machine (TM) 4 ## Standard TM to compute modulo and division of two natural numbers as well as to check if a given natural number is prime 5 ### STM as a transducer to compute modulo and division 6 7 Consider two numbers `u` and `v`. `u % v` is defined as `(u - v) % v`, if `u` is greater than or equal to `v` else, it is `u`. Using this, a recursive relation can be established, which is: 8 $\mod(u, v) = \begin{cases} u: u < v\\mod (u - v, v): otherwise\end{cases}$ 9 10 Its iterative code in JavaScript is: 11 12 ``` 13 function modulo(u, v) { 14 while(u >= v) 15 u = u - v; 16 return u; 17 } 18 ``` 19 Repeatedly subtracting yields remainder. However, if we count the number of times subtraction was performed, we get the quotient. Hence, modifying the above code slightly, quotient can be calculated: 20 21 ``` 22 function newModulo(u, v) { 23 var quo = 0; 24 while(u >= v) { 25 u = u - v; 26 quo++; 27 } 28 return u; 29 } 30 ``` 31 In the above code, `quo` variable gives the quotient. Noting that repeated subtraction yields remainder, and count of subtraction yields quotient, state transition diagram of a STM with tape of infinite memory (in theory) can be drawn. 32 33 __Refer figure 1 for TM1 which acts as a transducer to find remainder and quotient of two natural numbers__ 34 35 ### STM to check if entered natural number is prime or not 36 37 Consider a natural number `num`. If it is a composite number, it has atleast one factor between two and $\frac{num}{2}$, both inclusive. 38 39 What the STM is doing can be summed up in the following JavaScript code snippet: 40 ``` 41 function checkPrime(num) { 42 var div = Math.floor(num/2); 43 if(div == 0) 44 return 0; 45 while(div > 1) { 46 if(num % div == 0) 47 return 0; 48 div = div - 1; 49 } 50 return 1; 51 } 52 ``` 53 The above code requires modulo function, which is defined in the above secion, and the steps are provided in the Analysis section. A state transition diagram for the above logic can be drawn. 54 55 __Refer figure 2 for TM1 which acts as a transducer to find remainder and quotient of two natural numbers__ 56 57 ### Source code 58 ``` 59 // to be added tomorrow 60 ``` 61 62 ### Analysis 63 64 #### For calculation of remainder and quotient 65 66 Consider two numbers `a` and `b`, given that `a > b`, to perform `a - b`, keep decrementing `b` by one and `a` by one till `b` becomes `0`. 67 Implementing this in STM subtracting `1` from a number takes linear time. 68 69 Since calculation of modulo is subtracion of `v` from `u` until `u` is strictly smaller than `v`, procedure to obtain modulo by repeated subtraction, ie `u - v` is as follows: (__Assumption: Instruction pointer points to index 1__) 70 71 1. While current cell value is not `0`, move right. 72 2. If current cell value is `0`, go left. If it is `1`: Go right. Go right. Else, goto step #3 73 - Having travelled two right from reading `1`, if current cell is `1`: 74 - Go right until current cell is `B`. 75 - Move left until current cell is `1`. 76 - Mark it as `X`. 77 - Move left until current cell is `B`. 78 - Move right, make `1` as `B`. Goto step #1. 79 - Having travelled two right from reading `1`, if current cell is `X`, one subtraction is finished. (It's progress can be tracked, which will be mentioned later while dealing with quotient) 80 - Go right making all `X` as `1` until current cell is `B`. 81 - if current cell is `B` go left until current cell is `0`. Goto step #2. 82 3. If the current cell is `B`, go right, go right. If current cell is `X`, modulo is `0`. Stop. Else, goto step #4. 83 4. Having travelled two right from reading `B`, if the current cell is `1`, it simply means LHS number was smaller than RHS. In that case: 84 - Move right until current cell is `X`. 85 - Make current cell as `1`. 86 - Goto right until current cell is `B`. 87 - Make `B` as `1`. Repeat these four sub-steps until instruction pointer reaches `B` on the right hand side (or in other words, all `X` has been converted to `1`). 88 89 To find quotient, a small tweak should suffice. That is, "_Having travelled two right from reading `1`, if current cell is `X`, one subtraction is finished._" Make use of a different symbol in the array to distinguish second number from quotient (use another symbol, say `i` -- personal choice, really does not matter). After making all `X` as `1`, go right until current cell is `B`. Make `B` as `1`. Move right, make current symbol as `B`. Go left until current cell is `0`. Goto step #2. 90 91 #### To find if the number is prime 92 93 For an input `num`, the first step is to make a copy of $\lfloor\dfrac{num}{2}\rfloor$ start reading the tape from the beginning. (__Assumption: Instruction pointer points to index 0__) 94 95 1. For every second `1` encountered, mark it as `D`. 96 2. Move right until `B` is found. 97 3. Update `B` as `1`. 98 4. Move right and add `B` to the array. 99 5. Repeat steps 1 - 4 until instruction pointer reaches `0`. The complexity is observed to be linear time, ie $O(n)$. 100 101 Let the number copied towards the right-had side be called `div`. 102 103 1. Now, to compute modulo, follow the modulo procedure described in the previous section, perform `num % div`. If result of modulo is zero, stop. The number is not prime. 104 2. If the result of modulo was not zero, dercement `div` by one, which takes linear time (traversing till the end of tape, marking it as `B`, and coming back, which was mentioned in the preious section). Repeat the above step till `div` is greater than one. If `div` becomes one, `num` is prime. 105 106 The worst case is if `num` was a prime number. In that case, modulo has to be calculated from $\lfloor\dfrac{num}{2}\rfloor$ down to two, both inclusive. And computation of modulo depends on size of `div` as well as `num`. 107 108 ### Output 109 #### Result #1 110 #### Result #2 111 #### Result #3 112 #### Result #4 113 #### Result #5 114 #### Result #6 115 #### Result #7 116 #### Result #8 117 #### Result #9 118 #### Result #10 119 #### Result #11 120 #### Result #12 121 #### Result #13 122 #### Result #14 123 #### Result #15 124 #### Result #16 125 #### Result #17 126 #### Result #18 127 #### Result #19 128 #### Result #20