{"article":{"slug":"a-minsky-machine-in-ncurses-terminfo","title":"A Minsky machine in ncurses terminfo","subtitle":null,"summary":"Nicolas Seriot shows how ncurses terminfo parameter expansion can simulate a 2-counter Minsky machine—hosting a Fibonacci program in your terminal, clocked by /usr/bin/top.","content_type":"essay","language":"en","canonical_url":"https://seriot.ch/computation/terminfo/","author":{"name":"Nicolas Seriot","url":"https://seriot.ch/","person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"seriot.ch","url":"https://seriot.ch/","listing_slug":null,"listing":null},"topics":[{"name":"Programming","slug":"programming","url":"https://listedarticles.com/topics/programming"},{"name":"Open Source","slug":"open-source","url":"https://listedarticles.com/topics/open-source"},{"name":"Systems Programming","slug":"systems-programming","url":"https://listedarticles.com/topics/systems-programming"},{"name":"Tutorials","slug":"tutorials","url":"https://listedarticles.com/topics/tutorials"},{"name":"Research","slug":"research","url":"https://listedarticles.com/topics/research"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":1222,"reading_minutes":5,"published_at":"2026-10-02T00:00:00.000Z","added_at":"2026-10-04T20:09:44.785Z","updated_at":"2026-10-04T20:09:44.785Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/a-minsky-machine-in-ncurses-terminfo","markdown_url":"https://listedarticles.com/articles/a-minsky-machine-in-ncurses-terminfo.md","example":false,"citation":"Nicolas Seriot, seriot.ch. \"A Minsky machine in ncurses terminfo.\" 2 Oct 2026. https://seriot.ch/computation/terminfo/ (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://seriot.ch/computation/terminfo/"},"body_markdown":"*ncurses terminfo parameter expansion can simulate 2-counter Minsky machines.* \n\n*Host a parasite Fibonacci program in your terminal, clocked by /usr/bin/top.*\n\n*2nd October 2026*\n\nBack in 2019, Gwen Weinholt (weinholt.se) noticed that Terminfo featured a stack machine with parameters, arithmetic and logic, if-then-else, output, and persistent variables. Gwen noted that terminfo was close to a Turing machine but lacked loops, which could be worked around by pushing the iteration outside the language.\n\nMore recently, Martin Tournoij implemented the Go termfo package and noted that *\"terminfo files are Turing-complete\"*.\n\nThis article builds on these observations and makes the universality argument explicit with a reduction from two-counter Minsky machines.\n\nEarly physical terminals used various escape sequences to move cursor, delete characters, write in bold or colors, etc. Terminal applications need to know which escape sequences a terminal understands. The `$TERM` environment variable names a terminal type, and the terminfo database describes its capabilities. The database is actually a set of compiled keys and values, usually stored in `/usr/share/terminfo`.\n\nA typical macOS Terminal profile declares `TERM=xterm-256color`. Running `infocmp xterm-256color` shows, among other capabilities: `cup=\\E[%i%p1%d;%p2%dH`. `cup` is the key used for cursor addressing. Curses supplies zero-based row and column arguments, and `%i` increments the first two parameters, because the terminal escape sequence uses one-based coordinates.\n\nThe language is briefly presented in ncurses/tinfo/lib_tparm.c. Relevant bits for this article:\n\n| Instruction | Meaning | \n|---|---|\n| `%{n}` | push integer constant n | \n| `%gX` | push register X | \n| `%PX` | pop into register X | \n| `%=``%+``%-` | pop two, push equal / sum / subtraction | \n| `%d` | pop and print | \n| `%p1``%p2` | push the row and column args passed to cup, counted from 0 | \n| `%?c %t a %e b %;` | if c then a else b | \n| `%? c1 %t a1 %e c2 %t a2 %e b %;` | if c1 then a1, else if c2 then a2, else b | \n\nThe language uses 26 uppercase and 26 lowercase registers (`A-Z` and `a-z`). Uppercase registers are the ones meant to persist across various expansions inside a single process.\n\nThe interesting part is that we can use our own terminal conventions and define what happens when, say, curses is moving the cursor. In the following example, we compile a terminal named `test`, with a `cup` rule that prints `hello` at row 5, col 30, before moving the cursor to the requested position.\n\n```\ntest,cup=\\E[5;30H hello \\E[%i%p1%d;%p2%dH,\n```\nCompile and run with:\n\n```\ntic test.txt; TERM=test; tput cup 0 0\n```\nNote that, by default, tic commonly installs user entries under `~/.terminfo/`. To compile and look them up in the current directory instead, use `export TERMINFO=\"$PWD\"`.\n\nSo, we have a small language with arithmetic, persistent state and conditional control flow. As noted in section 1, it lacks an internal loop. Only repeated capability expansion can provide a clock.\n\nLet `A` and `B` be the two registers and `Z` the program counter.\n\nAn arbitrary instruction `i: INC A -> j` can be compiled as:\n\n```\nif Z == i:\n A = A+1\n Z = j\n```\nor in terminfo: `%gA%{1}%+%PA%{j}%PZ`.\n\nLikewise, `j: JZDEC A -> k, l` becomes:\n\n```\nif Z == j:\n if A == 0:\n Z = k\n else:\n A = A-1\n Z = l\n```\nWe can have a single `if / else-if` chain on `Z`, with one branch per instruction. Each expansion executes one machine step, and repeated expansions provide the clock.\n\nThis directly implements the instruction set of a two-counter Minsky machine. With idealized unbounded counters and capability size, **the construction is computationally universal**.\n\nIn practice, concrete ncurses implementations bound both register values and terminfo entry size, so any actual instance is finite-state.\n\nHere is a small adding machine, easy to inspect and understand. The machine computes 4 + 9 = 13. Each expansion prints the current state to stdout, and the program does not emit the final cursor-move escape.\n\nMinsky program:\n\n```\n0: A=4, B=9, Z=1 # initialization\n1: JZDEC B,3,2 # if B is empty, halt\n2: INC A,1 # move one unit from B into A\n3: HALT # halt\n```\n```\nadd,cup=\n# if (Z == 0) { A = 4; B = 9; Z = 1 }\n %?%gZ%{0}%=%t\n %{4}%PA\n %{9}%PB\n %{1}%PZ\n# else if (Z == 1) { if (B == 0) { Z = 3 } else { B = B-1; Z = 2 } }\n %e%gZ%{1}%=%t\n %?%gB%{0}%=%t\n %{3}%PZ\n %e\n %gB%{1}%-%PB\n %{2}%PZ\n %;\n# else if (Z == 2) { A = A + 1; Z = 1 }\n %e%gZ%{2}%=%t\n %gA%{1}%+%PA\n %{1}%PZ\n# else if (Z == 3) { HALTED }\n %e%gZ%{3}%=%t\n %;\n# print the trace after executing this expansion\n Z=%gZ%d A=%gA%d B=%gB%d\\n,\n```\nCompile and run by expanding the rules 20 times (the number of expansions the machine needs before halting):\n\n```\ntic add.txt\nTERM=add; yes 'cup 0 0' | head -n 20 | tput -S\n```\nLast line of output:\n\n```\nZ=3 A=13 B=0\n```\nAs with the addition machine, we can build a Fibonacci machine using 3 registers:\n\n```\nA = F(N-1)\nB = F(N)\nN = current Fibonacci index, also used as initialization flag\n```\n```\nfib,cup=\n %?%gN%{0}%=%t%{0}%PA%{1}%PB%{1}%PN\n %e%gA%gB%+%gB%PA%PB%gN%{1}%+%PN%;\n A=%gA%d B=%gB%d N=%gN%d F(%gN%d)=%gB%d\\r\\n,\n```\nThese lines mean:\n\n```\nif (N == 0) {\n A = 0; B = 1; N = 1;\n} else {\n stack: B' = A + B, A' = old B; N = N + 1;\n}\nprint trace line\n```\n```\ntic fib.txt\nTERM=fib; yes 'cup 0 0' | head -n 10 | tput -S\n```\nSo with head -n 10 the last line is:\n\n```\nA=34 B=55 N=10 F(10)=55\n```\nThe previous machine is clocked by `yes` which emits the same line repeatedly.\n\nAn interesting variant is to have another program providing the clock, be redrawing the screen at regular intervals.\n\nFor instance, `/usr/bin/top` redraws its header clock each second. On my setup, this causes a `cup(0,78)` call when the seconds field is repainted. This very cursor movement can be used as a clock (a clock to clock...). The exact coordinate depends on the `top` layout and terminal size.\n\n```\nfib_top,cup=\n# advance one step when top addresses the seconds digit at (0,78)\n %?%p1%{0}%=%p2%{78}%=%A%t\\\n %?%gN%{0}%=%t\\\n %{0}%PA%{1}%PB%{1}%PN\\\n %e\\\n %gA%gB%+%gB%PA%PB%gN%{1}%+%PN\\\n %;\\\n %;\n# show the current result in the window title\n \\E]0;F(%gN%d)=%gB%d\\007\n# emit the cursor move top requested\n \\E[%p1%{1}%+%d;%p2%{1}%+%dH,\n```\n```\ntic fib_top.txt\nTERM=fib_top; /usr/bin/top\n```\n*A parasitic Fibonacci program in your terminal, clocked by /usr/bin/top Output in window title.*\n\nIs it a bug? Nothing in the Fibonacci example needs to be broken. Arithmetic, conditionals, persistent variables, parameter expansion, and cursor addressing all behave as intended. The unexpected behavior emerges from their composition, which makes it a hack rather than a bug.\n\nThe interesting security property is the trust boundary: a user-controlled terminfo program is repeatedly interpreted by ncurses inside another process. But even when evaluated by a setuid-root program such as `top`, the Fibonacci program is not a privilege-escalation exploit. Terminfo parameter expansion cannot open files, execute commands, or issue syscalls.\n\nBy itself, the example only produces terminal output. Only a vulnerability in the terminfo parser or parameter evaluator in that privileged context could have a privileged impact.\n\nThis article demonstrates that:","body_html":"

ncurses terminfo parameter expansion can simulate 2-counter Minsky machines.

\n

Host a parasite Fibonacci program in your terminal, clocked by /usr/bin/top.

\n

2nd October 2026

\n

Back in 2019, Gwen Weinholt (weinholt.se) noticed that Terminfo featured a stack machine with parameters, arithmetic and logic, if-then-else, output, and persistent variables. Gwen noted that terminfo was close to a Turing machine but lacked loops, which could be worked around by pushing the iteration outside the language.

\n

More recently, Martin Tournoij implemented the Go termfo package and noted that "terminfo files are Turing-complete".

\n

This article builds on these observations and makes the universality argument explicit with a reduction from two-counter Minsky machines.

\n

Early physical terminals used various escape sequences to move cursor, delete characters, write in bold or colors, etc. Terminal applications need to know which escape sequences a terminal understands. The $TERM environment variable names a terminal type, and the terminfo database describes its capabilities. The database is actually a set of compiled keys and values, usually stored in /usr/share/terminfo.

\n

A typical macOS Terminal profile declares TERM=xterm-256color. Running infocmp xterm-256color shows, among other capabilities: cup=\\E[%i%p1%d;%p2%dH. cup is the key used for cursor addressing. Curses supplies zero-based row and column arguments, and %i increments the first two parameters, because the terminal escape sequence uses one-based coordinates.

\n

The language is briefly presented in ncurses/tinfo/lib_tparm.c. Relevant bits for this article:

\n
InstructionMeaning
%{n}push integer constant n
%gXpush register X
%PXpop into register X
%=%+%-pop two, push equal / sum / subtraction
%dpop and print
%p1%p2push the row and column args passed to cup, counted from 0
%?c %t a %e b %;if c then a else b
%? c1 %t a1 %e c2 %t a2 %e b %;if c1 then a1, else if c2 then a2, else b
\n

The language uses 26 uppercase and 26 lowercase registers (A-Z and a-z). Uppercase registers are the ones meant to persist across various expansions inside a single process.

\n

The interesting part is that we can use our own terminal conventions and define what happens when, say, curses is moving the cursor. In the following example, we compile a terminal named test, with a cup rule that prints hello at row 5, col 30, before moving the cursor to the requested position.

\n
test,cup=\\E[5;30H hello \\E[%i%p1%d;%p2%dH,
\n

Compile and run with:

\n
tic test.txt; TERM=test; tput cup 0 0
\n

Note that, by default, tic commonly installs user entries under ~/.terminfo/. To compile and look them up in the current directory instead, use export TERMINFO="$PWD".

\n

So, we have a small language with arithmetic, persistent state and conditional control flow. As noted in section 1, it lacks an internal loop. Only repeated capability expansion can provide a clock.

\n

Let A and B be the two registers and Z the program counter.

\n

An arbitrary instruction i: INC A -> j can be compiled as:

\n
if Z == i:\n    A = A+1\n    Z = j
\n

or in terminfo: %gA%{1}%+%PA%{j}%PZ.

\n

Likewise, j: JZDEC A -> k, l becomes:

\n
if Z == j:\n    if A == 0:\n        Z = k\n    else:\n        A = A-1\n        Z = l
\n

We can have a single if / else-if chain on Z, with one branch per instruction. Each expansion executes one machine step, and repeated expansions provide the clock.

\n

This directly implements the instruction set of a two-counter Minsky machine. With idealized unbounded counters and capability size, the construction is computationally universal.

\n

In practice, concrete ncurses implementations bound both register values and terminfo entry size, so any actual instance is finite-state.

\n

Here is a small adding machine, easy to inspect and understand. The machine computes 4 + 9 = 13. Each expansion prints the current state to stdout, and the program does not emit the final cursor-move escape.

\n

Minsky program:

\n
0: A=4, B=9, Z=1  # initialization\n1: JZDEC B,3,2    # if B is empty, halt\n2: INC A,1        # move one unit from B into A\n3: HALT           # halt
\n
add,cup=\n# if      (Z == 0) { A = 4; B = 9; Z = 1 }\n    %?%gZ%{0}%=%t\n        %{4}%PA\n        %{9}%PB\n        %{1}%PZ\n# else if (Z == 1) { if (B == 0) { Z = 3 } else { B = B-1; Z = 2 } }\n    %e%gZ%{1}%=%t\n        %?%gB%{0}%=%t\n            %{3}%PZ\n        %e\n            %gB%{1}%-%PB\n            %{2}%PZ\n        %;\n# else if (Z == 2) { A = A + 1; Z = 1 }\n    %e%gZ%{2}%=%t\n        %gA%{1}%+%PA\n        %{1}%PZ\n# else if (Z == 3) { HALTED }\n    %e%gZ%{3}%=%t\n    %;\n# print the trace after executing this expansion\n    Z=%gZ%d A=%gA%d B=%gB%d\\n,
\n

Compile and run by expanding the rules 20 times (the number of expansions the machine needs before halting):

\n
tic add.txt\nTERM=add; yes 'cup 0 0' | head -n 20 | tput -S
\n

Last line of output:

\n
Z=3 A=13 B=0
\n

As with the addition machine, we can build a Fibonacci machine using 3 registers:

\n
A = F(N-1)\nB = F(N)\nN = current Fibonacci index, also used as initialization flag
\n
fib,cup=\n    %?%gN%{0}%=%t%{0}%PA%{1}%PB%{1}%PN\n    %e%gA%gB%+%gB%PA%PB%gN%{1}%+%PN%;\n    A=%gA%d B=%gB%d N=%gN%d F(%gN%d)=%gB%d\\r\\n,
\n

These lines mean:

\n
if (N == 0) {\n    A = 0; B = 1; N = 1;\n} else {\n    stack: B' = A + B, A' = old B; N = N + 1;\n}\nprint trace line
\n
tic fib.txt\nTERM=fib; yes 'cup 0 0' | head -n 10 | tput -S
\n

So with head -n 10 the last line is:

\n
A=34 B=55 N=10 F(10)=55
\n

The previous machine is clocked by yes which emits the same line repeatedly.

\n

An interesting variant is to have another program providing the clock, be redrawing the screen at regular intervals.

\n

For instance, /usr/bin/top redraws its header clock each second. On my setup, this causes a cup(0,78) call when the seconds field is repainted. This very cursor movement can be used as a clock (a clock to clock...). The exact coordinate depends on the top layout and terminal size.

\n
fib_top,cup=\n# advance one step when top addresses the seconds digit at (0,78)\n    %?%p1%{0}%=%p2%{78}%=%A%t\\\n       %?%gN%{0}%=%t\\\n          %{0}%PA%{1}%PB%{1}%PN\\\n       %e\\\n          %gA%gB%+%gB%PA%PB%gN%{1}%+%PN\\\n       %;\\\n    %;\n# show the current result in the window title\n    \\E]0;F(%gN%d)=%gB%d\\007\n# emit the cursor move top requested\n    \\E[%p1%{1}%+%d;%p2%{1}%+%dH,
\n
tic fib_top.txt\nTERM=fib_top; /usr/bin/top
\n

A parasitic Fibonacci program in your terminal, clocked by /usr/bin/top Output in window title.

\n

Is it a bug? Nothing in the Fibonacci example needs to be broken. Arithmetic, conditionals, persistent variables, parameter expansion, and cursor addressing all behave as intended. The unexpected behavior emerges from their composition, which makes it a hack rather than a bug.

\n

The interesting security property is the trust boundary: a user-controlled terminfo program is repeatedly interpreted by ncurses inside another process. But even when evaluated by a setuid-root program such as top, the Fibonacci program is not a privilege-escalation exploit. Terminfo parameter expansion cannot open files, execute commands, or issue syscalls.

\n

By itself, the example only produces terminal output. Only a vulnerability in the terminfo parser or parameter evaluator in that privileged context could have a privileged impact.

\n

This article demonstrates that:

","headings":[]}}