Turing Machines as Functions

Learn about the various applications of Turing machines.

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

Get hands-on with 1400+ tech skills courses.