# How to find max number with a single-tape turing machine?

I'd appreciate hints for this problem

I'm trying to design a Turing Machine which calculates $\max \{x_1, x_2,..,x_k \}$.

Assuming $1 = 1^1; 2=1^2; n=1^n$ and all numbers/strings are separated by a blank character $B$.

• How would you program it?
– Raphael
Apr 7 '13 at 19:18

Start by finding $\max\{x_1,x_2\}$, and replacing $x_1,x_2$ with this new number. To do this, you can take to new symbols $X,Y$, and erase one letter from each number using one of $X,Y$. After one of the numbers is erased, you remain with the second number. You can then erase the smaller number, and restore the bigger one to $1$'s.