LaTeX is More Powerful than you Think - Computing the Fibonacci Numbers and Turing Completeness

Author: Robert Murrish (April 2012)

LaTeX is a powerful tool. So powerful in fact, that it can be used for much more than document markup. LaTeX is Turing complete; that is, it can be programmed to compute just about anything.

To demonstrate the general purpose programming abilities of LaTeX, we'll look at an example that calculates the first Fibonacci numbers. While this isn't a proof of Turing completeness, it is a good example of a complete algorithm implemented in LaTeX.

The Fibonacci Numbers

Each number in the Fibonacci sequence is the sum of the previous two terms in the sequence, with the first two terms defined as 1 to provide a starting point.

We can write a new command that will compute these numbers. Let's begin by deciding how a call to our yet-to-be-built command should look.

\fibonacci{10}

When this command is called from our LaTeX document, it should produce a list of n Fibonacci numbers (where n=10 in the example call here). Here is the code for the \fibonacci function. Let's take a look at how it works.

\newcount\temp
\newcount\fone
\newcount\ftwo
\newcount\counter

\newcommand{\fibonacci}[1]{
	\counter=#1
	\fone=1
	\ftwo=1
	\temp=0
	\the\fone, \the\ftwo
	\fibloop
}

\newcommand{\fibloop}{, 
	\let\next= \fibloop
	\temp=\fone
	\fone=\ftwo
	\advance\ftwo by \temp
	\ifnum\counter\let\next=\relax\else\advance\counter by -1\fi
	\the\ftwo
	\next
}

First, we set up a few variables that we'll use later. The \newcount command gives us a variable we can use to hold an integer, here we create four: \counter, \fone, \ftwo and \temp. It's worth mentioning that these are not actually new variables, they are more like aliases for counters that already exist. These can be used directly as \count0, \count1, etc. Assigning names prevents us from writing to a counter that is already is use. If you're curious, replace one of the variables in this code with \count0, and the page numbers will be wrong for the rest of the document.

We next have the \fibonacci command. We create it with \newcommand, which we provide with the name, number of arguments, and TeX code to process as arguments. For this program, we accept a single argument, the number of Fibonacci numbers to output. The content of this command is simple: we set default values for our variables, print the first two Fibonacci numbers (since they don't need to be calculated), and then call \fibloop, which will do the heavy lifting for our calculations.

The command \fibloop is declared in the same way. A key part of the program is the way in which it loops. We use a function called next, and you'll see that the first command within \fibloop sets this, and the last line calls it. We set \next to \fibloop, so the function will repeat until \next is changed by code within the \fibloop command. We only want to loop n times, so we use an if statement that checks the value of our counter, and then if it hasn't reached the threshold, decrements the counter value each time through the loop. If the condition is met, we set \next to \relax, which will prevent \fibloop from repeating again.

The other commands in this block calculate the next Fibonacci number in the sequence, and update the values of the variables so they're ready for the next pass. The command \the\ftwo prints the value of the current number to the document, you'll also notice a comma and a space at the top of the command to separate each value.

The Result

The simplest way to see this example in action is to copy the code above into the top of your .tex document, then add the line:

\fibonacci{n}

to the body of your document, replacing n with a number. The Fibonacci sequence grows quickly, so any n>46 will result in an integer overflow in this particular implementation. If you're using Overleaf, you can use the example main.tex as a starting point, and add this code to it.

Where to go from Here?

This was an example of the programming capabilities of LaTeX. As an informal proof that LaTeX is Turing complete, I present the following code:

\newcommand{\nand}[2]{
 \count0=#1
 \count1=#2
 \ifnum \count0=\count1 \ifnum\count0 0 \else 1 \fi\else 1 \fi
 }

which is a quick and dirty implementation of a NAND gate. NAND (and also NOR) logic gates have the interesting property that any other logic gate can be formed with just this single type of gate. From the basic logic gates latches, flip-flops, and memory can be created. Those are the ingredients for a general-purpose computer. You can test this NAND gate for each of its four possible inputs with the following code.

\nand{0}{0}
\nand{0}{1}
\nand{1}{0}
\nand{1}{1}

Knowing that LaTeX is Turing complete opens up a world of possibilities. Code like this is common in the back-end of LaTeX, for things like keeping track of page and figure numbers, and making decisions about where to place floats. It's a tool that you can use to your advantage to simplify complex document layouts.

To end this post, I'll leave you with some further reading on examples of programming in LaTeX and Turing machines in general.

LaTeX Programming Examples

Turing Machines in Unexpected Places

Overleaf guides

LaTeX Basics

Mathematics

Figures and tables

References and Citations

Languages

Document structure

Formatting

Fonts

Presentations

Commands

Field specific

Class files

Advanced TeX/LaTeX