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

Author: Robert Murrish (April 2012 (edited by Overleaf in April 2023))

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 to compute these numbers. Let’s begin by deciding how a call to our yet-to-be-written command might 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 command (i.e., LaTeX macro). Let’s take a look at how it works.

\documentclass{article}
\begin{document}

\newcount\temp
\newcount\fone
\newcount\ftwo
\newcount\fcnt

\newcommand{\fibonacci}[1]{%
	\fcnt=#1
	\fone=1
	\ftwo=1
	\temp=0
	\the\fone, \the\ftwo
	\let\next=\fibloop
	\fibloop
}

\def\fibloop{, %
	\temp=\fone
	\fone=\ftwo
	\advance\ftwo by \temp
	\ifnum\fcnt=0
            \let\next=\relax
        \else
            \advance\fcnt by -1
        \fi
	\the\ftwo
	\next
}

(\fibonacci{10})
\end{document}

 Open this example in Overleaf


First, we set up a few variables we’ll use later. The \newcount command gives us a variable we can use to hold an integer; here, we create four: \fcnt, \fone, \ftwo and \temp. It’s worth mentioning that these are not new variables; they are more like aliases for existing counters. LaTeX counters can be used directly as in \count0, \count1, etc. but assigning names to them prevents us from writing to a counter already in 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 command, we accept a single argument, the number of Fibonacci numbers to output. The content of this command is simple: we set initial 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 but a key part of this command is how it loops. We use a command called \next, initialized to \fibloop within \fibonacci, and used within \fibloop to control the looping. \fibloop will repeat until \next is changed by code within the \fibloop command itself. We only want to loop n times, so we use an \ifnum statement that checks the value of our counter (\fcnt) and then if it hasn’t reached the threshold value of 0, \fcnt is decremented each time the loop repeats. If the condition is met, we set \next to \relax, which will prevent \fibloop from repeating—the final \next command does nothing, and the loop terminates.

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 Fibonacci number to the document, and you’ll also notice a comma and a space at the top of the \fibloop command used to separate each value.

The Result

The simplest way to see this code in action is to run it on Overleaf using the Open this example in Overleaf link at the bottom of the code display. The Fibonacci sequence grows quickly, so any n>44 will result in an integer overflow in this particular implementation.

Where to go from here?

As an informal proof that LaTeX is Turing complete, I present the following code which is a quick-and-dirty implementation of a NAND gate:

\newcount\nanone
\newcount\nantwo

\newcommand{\nand}[2]{%
\nanone=#1
\nantwo=#2
  \ifnum\nanone=\nantwo
    \ifnum\nanone=0\relax 1
      \else 0
    \fi
   \else 1
\fi
}

NAND (and also NOR) logic gates have the interesting property that any other logic gate can be formed with this single type of gate. From the basic logic gates, you can construct latches, flip-flops, and memory. 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 example that you can open in Overleaf.

\documentclass{article}
\begin{document}

\newcount\nanone
\newcount\nantwo

\newcommand{\nand}[2]{%
\nanone=#1
\nantwo=#2
  \ifnum\nanone=\nantwo
    \ifnum\nanone=0\relax 1
      \else 0
    \fi
   \else 1
\fi
}

\nand{0}{0}
\nand{0}{1}
\nand{1}{0}
\nand{1}{1}
\end{document}

 Open this example in Overleaf


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 deciding 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 further reading on examples of programming in LaTeX and Turing machines.

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