The Turing-Completeness of TeX

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 II 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 λn.λf.λx.f (n f x)\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.