How to simulate a 3-stack automaton with a 2-stack automaton?

Question

Since a 2-stack automaton is Turing-equivalent, it is possible to simulate a 3-stack automaton with just a 2-stack automaton. But how so? How it is normally done?

Answer 1

To elaborate Jims comment:

Let the 2-stack automaton have stacks $1$ and $2$ and the 3-stack automaton we want to emulate have stacks $A,B$ and $C$.

At the beginning of an operation, stack 1 shall consist of elements from stack A paired with the symbol $a$, written as $(a,e_a)$ and stack 2 shall consist of entries $(m,e)$ where $m \in \{b,c\}$ and $e$ is an element of the respective stacks.

Valid beginning states of the emulator given the 3-stack automaton has $A = (1,2), B = (1,2), C = (1,2,3)$ can be $$S_1 = ((a,1),(a,2)) \\ S_2 = ((b,1), (c,1), (c,2), (b,2), (c,3))$$

POP
popping stack A is simple: just pop stack 1 and return the element

popping stack B or C:

1. Let $s$ be the corresponding marker of the stack to pop from ($b$ for stack $B$ and $c$ for stack $C$)
2. Let $(m,e)$ be popped from stack 2. If $m=s$, continue, else push $(m,e)$ onto stack 1 and redo 2.
3. Let $(n,g)$ be popped from stack 1. If $n=a$, push it back to stack 1 and return $e$. If not, push $(n,g)$ to stack 2. and redo 3.

PUSH
pushing $e$ to stack A is pushing $(a,e)$ to stack 1.
pushing $e$ to stack B is pushing $(b,e)$ to stack 2.
pushing $e$ to stack C is pushing $(c,e)$ to stack 2.

You should be able to see that all POP and PUSH operations return the automaton to a valid state and that POP and PUSH of all three stacks works as intended.

---

Pseudocode-ish version:

popA:
    (m,e) = pop1();
    return e;
popB:
    (m,e) = pop2();
    while m != b // This is the only difference to popC
        push1(m,e);
        (m,e) = pop2();
    (n,d) = pop1();
    while n != a
        push2(n,d);
        (n,d) = pop1();
    push1(n,d);
    return e;
popC:
    (m,e) = pop2();
    while m != c // This is the only difference to popB
        push1(m,e);
        (m,e) = pop2();
    (n,d) = pop1();
    while n != a
        push2(n,d);
        (n,d) = pop1();
    push1(n,d);
    return e;
pushA(e):
    push1(a,e);
pushB(e):
    push2(b,e);
pushC(e):
    push2(c,e);

Feel free to ask for further clarification.