# 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}
```

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}
```

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

- The Mandlebrot Set in LaTeX . Special thanks to this one; this code was a helpful example while writing my Fibonacci command.
- A Turing machine in LaTeX: the follow-up NB: When porting this article to another content-hosting system we noticed that the site referenced in the original article (http://en.literateprograms.org/Turing_machine_simulator_(LaTeX)) was no longer accessible, so we replaced that link with a follow-up article by another author.
- Wikibook on TeX commands
- LaTeX in a programming contest. A Mars rover controller in LaTeX beat out entries in several more common programming languages.

### Turing Machines in Unexpected Places

- Conway's Game of Life is Turing complete. Here is an implementation of a Turing machine.
- Rule 110 is a 1-D cellular automata that is Turing complete.
- Minecraft (the video game) is Turing complete. Several examples have been built, so the following link is simply to a page of relevant YouTube search results

## Overleaf guides

- Creating a document in Overleaf
- Uploading a project
- Copying a project
- Creating a project from a template
- Using the Overleaf project menu
- Including images in Overleaf
- Exporting your work from Overleaf
- Working offline in Overleaf
- Using Track Changes in Overleaf
- Using bibliographies in Overleaf
- Sharing your work with others
- Using the History feature
- Debugging Compilation timeout errors
- How-to guides
- Guide to Overleaf’s premium features

## LaTeX Basics

- Creating your first LaTeX document
- Choosing a LaTeX Compiler
- Paragraphs and new lines
- Bold, italics and underlining
- Lists
- Errors

## Mathematics

- Mathematical expressions
- Subscripts and superscripts
- Brackets and Parentheses
- Matrices
- Fractions and Binomials
- Aligning equations
- Operators
- Spacing in math mode
- Integrals, sums and limits
- Display style in math mode
- List of Greek letters and math symbols
- Mathematical fonts
- Using the Symbol Palette in Overleaf

## Figures and tables

- Inserting Images
- Tables
- Positioning Images and Tables
- Lists of Tables and Figures
- Drawing Diagrams Directly in LaTeX
- TikZ package

## References and Citations

- Bibliography management with bibtex
- Bibliography management with natbib
- Bibliography management with biblatex
- Bibtex bibliography styles
- Natbib bibliography styles
- Natbib citation styles
- Biblatex bibliography styles
- Biblatex citation styles

## Languages

- Multilingual typesetting on Overleaf using polyglossia and fontspec
- Multilingual typesetting on Overleaf using babel and fontspec
- International language support
- Quotations and quotation marks
- Arabic
- Chinese
- French
- German
- Greek
- Italian
- Japanese
- Korean
- Portuguese
- Russian
- Spanish

## Document structure

- Sections and chapters
- Table of contents
- Cross referencing sections, equations and floats
- Indices
- Glossaries
- Nomenclatures
- Management in a large project
- Multi-file LaTeX projects
- Hyperlinks

## Formatting

- Lengths in LaTeX
- Headers and footers
- Page numbering
- Paragraph formatting
- Line breaks and blank spaces
- Text alignment
- Page size and margins
- Single sided and double sided documents
- Multiple columns
- Counters
- Code listing
- Code Highlighting with minted
- Using colours in LaTeX
- Footnotes
- Margin notes

## Fonts

## Presentations

## Commands

## Field specific

- Theorems and proofs
- Chemistry formulae
- Feynman diagrams
- Molecular orbital diagrams
- Chess notation
- Knitting patterns
- CircuiTikz package
- Pgfplots package
- Typesetting exams in LaTeX
- Knitr
- Attribute Value Matrices

## Class files

- Understanding packages and class files
- List of packages and class files
- Writing your own package
- Writing your own class