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^{A}T_{e}X to do it.

Unfortunately, it is well-known that T_{e}X^{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 T _{e}X?*

My original inspiration was actually Tom Wildenhain’s wonderful demonstration of the Turing-completeness of Power Point^{4}. 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_{e}X. Well, after spending a bit learning about the low-level details of T_{e}X, 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_{e}X 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^{5}:

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

In this post, my examples are all plain T

_{e}X rather than L^{a}T_{e}X, 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

_{e}X 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.↩︎

## Comments