Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 59 Β· Context-Sensitive and Other Models

Counter Machines, Two-Stack Machines and Other Models

Explore automata beyond the PDA: counter machines, two-stack machines and queue automata, and why two stacks already equal a Turing machine. Python demos included.

So far each machine we met was a finite control plus one kind of memory: nothing (finite automaton), one stack (PDA), or a bounded tape (LBA). What happens if we change the memory? Computer scientists have tried counters, several stacks, queues and more. The answers form a map of computational power with a surprising landmark: two stacks are already as powerful as a Turing machine. This lesson walks through the most important variants and demonstrates the key equivalences in code.

Memory decides the power

No memory Finite automaton. Regular languages.
One counter Counts up and down. Fits a^n b^n only.
One stack Pushdown automaton. Context-free.
Two stacks As strong as a Turing machine.

A queue, or two counters, are also enough for everything computable.

1 / 2

One-counter automata

A counter is a stack with only one symbol: you can add one, subtract one, and test whether it is zero. A one-counter automaton recognizes a^n b^n and similar languages (push As, pop As), but not palindromes, because the counter cannot remember which letters were read, only how many. So one counter is strictly between finite automata and PDAs.

Machines with two stacks

Give a finite control two stacks, and the picture changes completely. A Turing machine's tape can be cut at the head position:

  • everything left of the head goes onto stack 1 (nearest cell on top);
  • the cell under the head and everything right of it go onto stack 2 (head cell on top).

Moving the head right pops the head cell from stack 2 and pushes the written symbol onto stack 1; moving left does the reverse. One Turing machine step costs a constant number of stack operations. Hence a two-stack automaton is exactly as powerful as a Turing machine, while a single stack is not.

flowchart LR
    L["stack 1<br/>cells left of the head<br/>(top = nearest)"] <--> H(["finite control<br/>+ head cell"]) <--> R["stack 2<br/>cells right of the head<br/>(top = head cell)"]

Moving the head means moving one symbol from one stack to the other.

The code below runs the same Turing machine rules twice: once on an ordinary tape and once on two stacks, and compares the results on every binary string up to length 8. The rules implement 0^n 1^n by marking symbols (you will study this machine in the next chapter's first lesson).

Python A Turing machine on two stacks

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two simulations agree everywhere, including the number of steps. A single stack cannot do this, because it has no way to move "down" to inspect what lies below the top without destroying it.

Counter machines (Minsky machines)

A counter machine has a finite control and a few registers that hold non-negative integers. There are only three kinds of instructions:

  • inc r: add 1 to register r;
  • dec r, Z: if r > 0, subtract 1; otherwise jump to Z;
  • halt.

That is all, yet:

Minsky's theorem. Two counters are enough to simulate any Turing machine.

Idea: encode each stack as a number. A stack of digits d1 d2 … dk over a base-b alphabet is the integer d1 + bΒ·d2 + bΒ²Β·d3 + …. Push is "multiply by b and add the digit", pop is "divide by b and look at the remainder". Multiplication and division can be done by looping with counters. Three or more counters are easy; Minsky shows how to merge them into two with GΓΆdel-style encoding 2^x Β· 3^y Β· 5^z.

Python Counter machine programs: addition and multiplication

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The program MUL shows the usual technique: copy a register into a temporary while using it, then restore it. The integer-stack demo shows how a whole stack of symbols hides inside one counter.

Queue automata

A queue automaton keeps a first-in-first-out queue instead of a stack: it reads from the front and appends at the back. A queue lets the machine rotate through its memory, which is exactly what comparing w with w (copy language) needs. One queue is already enough to simulate a Turing machine, so queue automata are as powerful as Turing machines too.

Summary of the power ladder

Machine Memory Recognizes
DFA / NFA none regular
One-counter automaton one counter a proper subset of context-free
PDA one stack context-free
DPDA one stack, deterministic deterministic context-free
LBA tape bounded by input context-sensitive
Two-stack automaton two stacks recursively enumerable
Two-counter machine two counters recursively enumerable
Queue automaton one queue recursively enumerable
Turing machine infinite tape recursively enumerable

There is a sharp boundary between one and two of the same resource. One stack, no; two stacks, everything. Likewise one counter is weak, two counters are universal. A small architectural change can cross the line from "decidable questions" to "undecidable ones".

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. How does a two-stack automaton simulate a Turing machine tape?

    Moving the head just moves one symbol from the top of one stack to the top of the other.
  2. 2. What can a one-counter automaton NOT recognize?

    A counter remembers how many, not which; palindromes need to remember the sequence.
  3. 3. Which of the following is true of Minsky's theorem?

    Counters can encode stacks as integers, so two counters can emulate a full Turing machine.
  4. 4. What is special about a queue automaton compared with a PDA?

    First-in-first-out access lets the machine copy and compare in the same order, which a stack cannot.

Summary

  • The power of an automaton comes mostly from its memory: none, a counter, a stack, a bounded tape, or something richer.
  • One-counter automata sit below PDAs; palindromes are out of their reach.
  • Two stacks, two counters or one queue are each as powerful as a Turing machine.
  • Minsky machines have just inc, dec/test and halt and still compute everything computable.

Next: Turing machine basics