# 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

- 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 aricle (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 which 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