# The Turing-Completeness of TeX October 18, 2020

So the other day I was trying to make a resume, since, as much as I hate it, it’s something that one should do as an undergrad. My original setup was to write it in some HTML to “easily” maintain both a web version and print version at the same time. As it turns out, I can’t be bothered to keep an updated web version; I figured that if I only needed a print version, I might as well just use to do it.

Unfortunately, it is well-known that 1 is Turing complete. So I couldn’t help but think to myself: wouldn’t it be pretty funny if someone made a Turing machine in ?2 Naturally, I had to spend the next few hours trying to make a Turing machine in rather than, you know, writing a resume.3

My original inspiration was actually Tom Wildenhain’s wonderful demonstration of the Turing-completeness of Power Point4. I have neither the programming ability nor the patience of Tom, so I figured that I’d go for some lower-hanging fruit and try to implement a Turing machine in . Well, after spending a bit learning about the low-level details of , I realized that I also do not have the patience to implement a Turing machine in it. Instead, I decided to settle for an even easier goal: implementing the SKI combinator basis, which is also sufficient to show Turing-completeness. The idea was adapted from Stack Overflow to allow for partial application of combinators:

\catcode' = 11

\def\K#1{\K'#1}
\def\K'#1#2{#1}

\def\S#1{\S'#1}
\def\S'#1#2{\S''#1#2}
\def\S''#1#2#3{#1#3{#2#3}}

(I’m 90% sure that there’s a bug related to macro expansion here, but I’m not good enough with to figure it out.) For example, you can define the identity combinator $I$ and verify that it just does the identity:

\def\I{\S{\K\K}}
\I{x}  % will print "x"

You can also define numbers encoded as Church numerals5:

\def\succ{\S{\K\S}{\S{\S}{\K\I}}}
\def\zero{\K\I}
\def\one{\succ\zero}
\def\two{\succ\one}
\def\three{\succ\two}
\def\four{\succ\three}

And you can print them in unary (I was going to print them in decimal, but the aforementioned bug made it difficult to do so):

\def\display#1{1#1}
\def\unary#1{
\edef\numstring{#1{\display}{\empty}}
\ifx\empty\numstring
0
\else
\numstring
\fi
}
\unary{\zero}  \par  % "0"
\unary{\one}   \par  % "1"
\unary{\two}   \par  % "11"
\unary{\three} \par  % "111"
\unary{\four}  \par  % "1111"

And, if you’re feeling brave, you can even run an infinite loop:

\def\loop{\S\I\I}
\loop{\loop}`

1. In this post, my examples are all plain rather than , for no particular reason.↩︎

2. So a quick Google search reveals that this has been done before, but hey, there’s nothing new under the sun.↩︎

3. Don’t worry, I did eventually write that resume, like more than a month later.↩︎

4. See SIGBOVIK 2017 proceedings.↩︎

5. Converting the successor function $\lambda n. \lambda f. \lambda x. f~(n~f~x)$ into the SKI basis was fun. I at first tried to automate the process, but the end result wouldn’t work properly, probably because my was buggy. I then sat down and did it the old-fashioned way, using some “intuition” (i.e. guess and check) to keep the final expression size small enough to be tenable. Fun fact: showing that any lambda expression can be written in the SKI basis was a homework problem in 15-252. I did not fully solve that homework problem.↩︎