Remainder of division on a Turing machine?

Question

Programming

tell me how to implement this task, no ideas.

Answer 1

In general, I recommend that you first estimate the algorithm in natural language, in the sense of how it could be: We get
up on%.
While there is 1 in the divisor, we replace it with X, and replace one 1 in the dividend with Y. If there are no units in the dividend (there is nothing to replace with Y), then we transfer all Y as 1 to the cells after "->". This is the answer.
When all 1s are replaced by X in the divisor, we replace them back with 1 and check if there are still 1s left in the dividend.
If there are units left in the dividend, we replace all Y with 0, get up on% and start all over again.
If there are no units left in the dividend, then we transfer all the remaining Y in the form of 1 to the cells after "->". This is the answer.
There was a mistake. We have just successfully finished subtracting another divisor, and there is nothing left in the dividend. This means that it is completely divided.
I won't say it's optimal, but it will work. Maybe some more corner cases need to be considered, but the idea should be clear. In fact, you simply subtract the divisor from the dividend until the dividend becomes less than the divisor.
Now each of these rules must be formalized as a set of rules for MT. Of course, there are no all these "when / if / then" in the MT, so you have to emulate them by transitions to the corresponding state. It's not difficult, but there can be a lot of rules. For example, the simple phrase "While there is a 1 in the divisor, replace it with X, and replace one 1 in the dividend with Y." will be deployed in 3-5 states.
Plus, this algorithm corrupts the original data. If you cannot spoil them, then you must first copy them to another place on the tape, and then do not forget to "tidy up" by removing the remaining garbage.