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

Problem Detail: 

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$.

Asked By : Iancovici

Answered By : Shaull

There are many ways to tackle this. This is just one suggestion. I assume you need a single-tape machine, and that you actually need to write it down formally, so you need a very simple solution, not something like "just compare the numbers".

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.

Then, simply repeat the process until you are left with a single number. It requires several states, but it shouldn't be too huge.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11107