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 ScribTeX, 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 [http://warp.povusers.org/MandScripts/latex.html]. Special thanks to this one, this code was a helpful example while writing my Fibonacci command.

Turing Machine Simulator in LaTeX [http://en.literateprograms.org/Turing_machine_simulator_(LaTeX)]. This is a Turing machine that creates a description of its state as it runs the 3-state busy beaver problem.

Wikibook on TeX commands [http://en.wikibooks.org/wiki/Category:TeX]. 

LaTeX in a programming contest [http://sdh33b.blogspot.com/2008/07/icfp-contest-2008.html]. 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 [http://rendell-attic.org/gol/utm/index.htm]. Here is an implementation of a Turing machine.

Rule 110 [http://en.wikipedia.org/wiki/Rule_110] is a 1-D cellular automata which is Turing complete.

Minecraft (the video game) is Turing complete [http://www.youtube.com/results?search_query=minecraft+turing+machine]. Several examples have been built, so this link is simply to a page of relevant youtube search results.

 

 

Posted by Robert Murrish on 24 Apr 2012