Design a Turing machine that takes input two non-negative numbers and performs the mod operation on them, for example, mod(3,7)=3 and mod(7,3)=1. Clearly, specify any assumptions and formats about the input and output of the TM.
Input is two positive integers X and Y in unary separated by a separator symbol. Output is a single number Z in unary. TM is single sided single tape deterministic.
First, move right to find the separator. Then, bounce back and forth between the end of X and the beginning of Y, marking pairs of symbols. If you run out of X before running out of Y, then X < Y and X mod Y = X; erase the separator and everything after it, then change all tape symbols to your unary digit and halt-accept. If you run out of Y before X, then change marked symbols in X to erased/separator, restore marked symbols of Y to the unary digit, and repeat (X >= Y, so X mod Y = (X - Y) mod Y).
Here's how your 2 mod 3 gets processed:
#110111#
#1a0b11#
#aa0bb1#
#aa#####
#11#####
Here's how 3 mod 2 gets processed:
#111011#
#11a0b1#
#1aa0bb#
#100011#
#a000b1#
#a######
#1######