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 L^AT_eX to do it.

Unfortunately, it is well-known that T_eX¹ 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 T_eX?² Naturally, I had to spend the next few hours trying to make a Turing machine in L^AT_eX rather than, you know, writing a resume.³

My original inspiration was actually Tom Wildenhain’s wonderful demonstration of the Turing-completeness of Power Point⁴. 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 T_eX. Well, after spending a bit learning about the low-level details of T_eX, 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 T_eX 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"

\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"

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

In this post, my examples are all plain T_eX rather than L^aT_eX, for no particular reason.↩︎
So a quick Google search reveals that this has been done before, but hey, there’s nothing new under the sun.↩︎
Don’t worry, I did eventually write that resume, like more than a month later.↩︎
See SIGBOVIK 2017 proceedings.↩︎
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 T_eX 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.↩︎

The Turing-Completeness of TeX October 18, 2020