Over a month ago I gave a talk about Turing machines in LaTeX at one of our ACM Student Chapter's TechTalks. When spreading the word about it, some people thought I was going to discuss how to draw Turing machines in LaTeX. At first that idea seemed so silly I wondered why they would think so. But apparently me live TeX'ing finite state automata and Turing machines in class made an impact on people, which made me known as "the guy who does Turing machines in TeX". Ahh, those days are gone forever, and quite frankly I'm happy they are, there are packages more fun to play with than gastex *shivers*.

Anyway, enough for this trip down memory lane. So I was going to present an implementation of a Turing machine in LaTeX. Luckily, Turing machine simulator (LaTeX) is an article about an actual implementation which I thankfully used. This resulted in these slides.

This post is about what happened at the presentation: the introduction was too terse. Not that I introduce too many concepts: the audience consisted of computer science students, they know what a Turing machine is, but the need for a busy beaver went above people's heads. Even stating several times that there is no need for it, it's just an interesting kind of Turing machine, seemed to make no impact. Understanding what it is, not the biggest problem, understanding why it was not necessary for the point I was trying to make, impossible :). If I ever do this talk again, I have to make sure to anticipate this.

Grasping how the TeX code actually works wasn't a problem on the other hand. It's quite a strange paradigm for a room full of C++ afficionados (our university's curriculum lacks other paradigms, oh I would've loved a full-fledged Lisp course) and the syntax is of course nothing they've ever seen, but apparently TeX is easier than I thought or me running around and drawing stuff actually helps understanding.

At the end of the talk I was going to run pdflatex on the file and show the output, as most people have never seen TeX from the commandline. So far so good, I knew the code would build. Then came the question. Does it simulate other Turing machines as well? Because okay, you've got your busy beaver implemented, you said it could simulate any Turing machine. Unprepared demo's, the horror. But it went smooth, I just changed one cell of the transition table and I got a halting Turing machine! Point proven. They now believed me it could simulate any Turing machine.

And now I was wondering what TeX would do when faced with a machine that doesn't halt. I changed line 64 from the code to 

\newcommand{\Azero}{\Write{one}\Moveright\State{A}}
so it will just move right and write ones. When faced with this Turing machine TeX produces 6473 pages (it doesn't actually write them, unfortunately) before halting with 
! TeX capacity exceeded, sorry [hash size=65000].
\ReadTape ...me TapeAt\arabic {headpos}\endcsname
                                                  \ifx \TapeAtHead \relax \e...
l.83 \RunTuringMachine

!  ==> Fatal error occurred, no output PDF file produced!
Transcript written on turing.log.
All this magic happened in 
real	0m22.199s
user	0m21.610s
sys	0m0.260s

What happened? Every cell of the tape that is read expands to a control sequence containing the value. This means that after 22 seconds there are 65000 so called multiletter control sequences in use which is my installation's limit.

turing.log contains the following statement by the way: 

If you really absolutely need more capacity,
you can ask a wizard to enlarge me.

The 80s, when software still could be funny...