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
