Turing Machines as Functions

Turing machines can also act as functions by leaving output on the tape. The following $\text{TM}$ computes $n \;\text{mod}\; 2$. We encode numbers in unary notation, so $1 = 1, 2 = 11, 3 = 111$, etc. The idea is to use two states for evenness vs. oddness and then leave either a $0$ or $1$ on the tape.

States $q_2$ and $q_3$ change all $1$'s to blanks. The $q_4$ state is the halt state. When a number is even, a blank will eventually appear while in state $q_0$, so we erase all the $1$’s and leave a $0$ on the tape. From $q_1$, we end up leaving a $1$. There is no need for an accepting state since the machine produces output.

Adding two numbers

It is easy to add ...