3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ How would you program it? $\endgroup$ – Raphael Apr 7 '13 at 19:18
9
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.