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

You can also define numbers encoded as Church numerals⁵:

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