commit01e9a16dbd662d0bb5ff777601297452eae8a393parenta573111c587fa6e98050a005b3cdf663feff4befAuthor:Agastya Chandrakant <acagastya@outlook.com>Date:Mon, 16 Apr 2018 22:04:39 +0530 addDiffstat:

M | s4/fafl/report.md | | | 11 | +++++++++-- |

1 file changed, 9 insertions(+), 2 deletions(-)diff --git a/s4/fafl/report.md b/s4/fafl/report.md@@ -34,7 +34,7 @@ __Refer figure 1 for TM1 which acts as a transducer to find remainder and quotie ### STM to check if entered natural number is prime or not -Consider a natural number `num`. If it is a composite number, it has atleast one factor between two and $\frac{num}{2}$, boh inclusive. +Consider a natural number `num`. If it is a composite number, it has atleast one factor between two and $\frac{num}{2}$, both inclusive. __Refer figure 2 for TM1 which acts as a transducer to find remainder and quotient of two natural numbers__ @@ -50,7 +50,7 @@ __Refer figure 2 for TM1 which acts as a transducer to find remainder and quotie Since calculation of modulo is subtracion of `v` from `u` until `u` is strictly smaller than `v`, procedure to follow `u - v` is as follows: (__Assumption: Instruction pointer points to index 1__) 1. While current cell value is not `0`, move right. -2. If current cell value is `0`, go left. If it is `1`: Go right. Go right. +2. If current cell value is `0`, go left. If it is `1`: Go right. Go right. Else, goto step #3 - If it is `1`: - Go right until current cell is `B`. - Move left until current cell is `1`. @@ -60,6 +60,13 @@ Since calculation of modulo is subtracion of `v` from `u` until `u` is strictly - If it is `X`, one subtraction is finished. (It's progress can be tracked, which will be mentioned later while dealing with quotient) - Go right making all `X` as `1` until current cell is `B`. - if current cell is `B` go left until current cell is `0`. Goto step #2. +3. If the current cell is `B`, go right, go right. If current cell is `X`, modulo is `0`. Stop. Else, goto step #4. +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: + - Move right until current cell is `X`. + - Make current cell as `1`. + - Goto right until current cell is `B`. + - Make `B` as `1`. Repeat these four sub-steps until instruction pointer reaches `B` on the right hand side. + #### To find if the number is prime 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__)