# Typesetting the entire Song That Never Ends

I've heard that LaTeX (and for that matter TeX) are Turing-complete, so it should be possible to produce an infinite loop. And indeed, a quick search reveals several questions in which users have found infinite loops--but these were always for subtle reasons and rather indecipherable to someone just wanting to see a basic loop construction. (I suppose that "transparent" infinite loops are usually solved by the programmer without having to ask here.)

Hence, my question: How do you produce an infinite loop in a way that is enlightening to someone to whom the Turing-completeness of LaTeX feels like a myth?

Or, just to spice it up a bit: How do you tell LaTeX to print all infinitely many verses of "The Song That Never Ends"?

[Note: I conceived of a version of this question some time ago--long before I knew the answer--but never got around to posting it. I am interested in seeing approaches besides the one I eventually came up with myself.]

-
\def\foo{\foo}\foo? –  cgnieder Jan 29 '13 at 0:38
@cnieder: That sort of solution is precisely the reason I did not post the question back when I thought of it. I want an infinite loop that actually looks at least a little like a loop, and/or does something mildly interesting. –  Charles Staats Jan 29 '13 at 1:24
\count255=0 \loop\ifnum\count255>0 Print something\endgraf\repeat –  egreg Jan 29 '13 at 10:44
@CharlesStaats Metafont and Metapost have a forever primitive loop. –  egreg Jan 30 '13 at 10:50
"I've heard that LaTeX (and for that matter TeX) are Turing-complete". Had to point out that since LaTeX runs on top of TeX, TeX has to be Turing-complete if LaTeX is. I find it more surprising that LaTeX is Turing-complete. Is it even true, if we stick to the LaTeX commands and avoid dropping down to TeX, as we're supposed to? –  alexis Mar 23 at 13:57

Edit: To give some indications for this question (What's the maximum number of pages a PDF produced by pdfTeX can have?), I tried my second version with a limit of 2.500.000 pages. The PDF produced (in approximatively 30 minutes) contains 1112672090 bytes.

Here is a variation of your first solution (this document can't be terminated!):

\documentclass{article}
\title{The Song That Never Ends}
\author{by Norman Martin}

\def\songthatneverend{
\noindent This is the song that never ends. \newline
Yes, it goes on and on my friends. \newline
Some people started singing it not knowing what it was, \newline
and they'll continue singing it forever just because

\expandafter\songthatneverend}

\begin{document}
\maketitle
\songthatneverend
\end{document}


And a version with a limited number of pages (25000 pages => 11MiB PDF):

\documentclass{article}
\usepackage{etoolbox}
\title{The Song That Never Ends}
\author{by Norman Martin}

\def\songthatneverend#1{
\noindent This is the song that never ends. \newline
Yes, it goes on and on my friends. \newline
Some people started singing it not knowing what it was, \newline
and they'll continue singing it forever just because

\ifnumless{\value{page}}{#1}{\def\cont{\expandafter\songthatneverend{#1}}}{\def\cont{}}\cont
}

\begin{document}
\maketitle
\songthatneverend{25000}
\end{document}

-
My cpu was using 32%. After 25000 pages I kill the process. lol –  Sigur Jan 29 '13 at 1:26
[2632390] [2632391] [2632392] [2632393] [2632394] [2632395] [2632396] [2632397] [2632398] [2632399] [2632400] [2632401] [2632402] [2632403] [2632404] [2632405] [2632406] [2632407 ! TeX capacity exceeded, sorry [indirect objects table size=8388607]. <to be read again> \endgroup \set@typeset@protect l.16 \end{document} ! ==> Fatal error occurred, no output PDF file produced! Transcript written on x.log. –  math Apr 2 '13 at 7:56

The following code will do what is asked, using the plain TeX construction \loop ... \if ... \repeat:

\documentclass{article}
\title{The Song That Never Ends}
\author{by Norman Martin}
\begin{document}
\maketitle
%
\noindent This is the song that never ends. \newline
\loop \iftrue
Yes, it goes on and on my friends. \newline
Some people started singing it not knowing what it was, \newline
and they'll continue singing it forever just because

\noindent this is the song that never ends. \newline
\repeat
%
\end{document}


I ran this code once, and aborted the process after it reported producing something like 47,000 pages (in a very short amount of time). Unfortunately, my computer complained that the resulting pdf file was "damaged" and could not be opened. A better (perhaps impossible?) answer would produce a file such that the output could actually be viewed once the process was killed (or died). The closest I've come is the following, which prints only the first five hundred verses:

\documentclass{article}
\title{The Song That Never Ends}
\author{by Norman Martin}
\begin{document}
\maketitle
%
\noindent This is the song that never ends. \newline
\newcounter{repetitions}
\setcounter{repetitions}{0}
\loop \ifnum \value{repetitions}<500
Yes, it goes on and on my friends. \newline
Some people started singing it not knowing what it was, \newline
and they will go on singing it forever just because

\noindent this is the song that never ends. \newline
\repeat
%
\end{document}


I'd be interested to see other versions.

-

Here is a never ending counting of the primes... (except that it will end-up in some arithmetic overflow error after a while).

For less overhead, I use plain PDFTeX. Launching the run in a Terminal, the page numbers correspond to how many primes have been computed so far.

update: the algorithm was a bit faulty, although it computed correctly the primes. The tested integer n had to receive from time to time a +2 kick that was missing, so that the amount of divisions done slowly drifted above the necessary. Furthermore my imprudent use of \1,\2, .. gave unwanted space tokens in the output (this was very silly on my part, but I have learned my lesson).

..........(terminal output until ^C interrupt)...........
[150451] [150452] [150453] [150454] [150455] [150456] [150457] [150458]
[150459] [150460] [150461] [150462] [150463] [150464] [150465] [150466]
[150467] [150468] [150469] [150470] [150471]^C
! Interruption.
\TestDiv
\TestDiv ...expandafter \expandafter \TestDiv \fi
\fi
\ToLogIfPrime ->\e \1 \TestDiv
\ifnum \e >\k \write \mone {\the \n }\the \n ...

\CheckNs ...m \j <\k \advance \n \2 \ToLogIfPrime

\FindPrimes ->\j \0 \CheckNs
l.73 \FindPrimes

? X
</usr/local/texlive/2012/texmf-dist/fonts/type1/public/amsfonts/cm/cmr10.pfb>
Output written on primes.pdf (150471 pages, 28821382 bytes).
Transcript written on primes.log.


The file primes.pdf is not corrupted here are the last pages for this run:

Ah, and some confirmation:

    |\^/|     Maple 12 (IBM INTEL LINUX)
._|\|   |/|_. Copyright (c) Maplesoft, a division of Waterloo Maple Inc. 2008
<____ ____>  Waterloo Maple Inc.
|       Type ? for help.
> ithprime (150471);
2021959


Also, the code writes the primes into the log file: (I don't know the origin of some additional linebreaks in the log file, like here just above page number 150467)

] [150461
2021807
] [150462
2021837
] [150463
2021839
] [150464
2021843
] [150465
2021849
] [150466
2021863
]
[150467
2021879
] [150468
2021891
] [150469
2021927
] [150470
2021933
] [150471
2021959
]
! Interruption.


Here is the code (just the basic algorithm of testing for divisors until square root of n, without adornments; and minus an unfortunate oversight of the previous version, as explained above):

% Time-stamp: <30-01-2013 19:19:16 CET jfbu>

% file primes.tex to find and count prime numbers

% page geometry
\pdfoutput = 1
\hoffset = -2.44cm
\voffset = -2.44cm
\pdfpagewidth = 7cm
\pdfpageheight = .7cm
\hsize 6.8cm
\vsize .5cm
\parindent 0pt
\footline {}

\chardef\zero 0
\chardef\one 1
\chardef\two 2

\newcount\mone
\mone = -1

\newcount\n
\newcount\m
\newcount\e
\newcount\k
\newcount\j

\def\TestDiv{%
\ifnum\e>\k\else
\m\n
\divide\m\e
\multiply\m\e
\ifnum\m=\n \else
\expandafter\expandafter\expandafter
\TestDiv
\fi
\fi}

\def\ToLogIfPrime{\e\one
\TestDiv
\ifnum\e>\k
%                    \write\sixteen{\the\n}\leavevmode\vfill\eject
\write\mone{\the\n}\the\n\ (\the\count\zero)\vfill\eject
\fi}

\def\CheckNs{%
\ifnum\j<\k
\expandafter\CheckNs
\fi}

\def\FindPrimes{%
\j\zero          % k is even,
\CheckNs         % we scan the k odd n's  such that k^2 < n < (k+1)^2
\advance\k\one   % now k is odd and the next odd n is k^2
\advance\n\two   % which certainly is not prime.
\j\zero
\CheckNs         % from k^2+2 up to (k+1)^2 - 1, this makes k n's to go
%\ifnum\k<100 % <- set this if you want finite computation
%\expandafter
\FindPrimes
%\fi
}

\k 2
\n 3

\write-1{2}2 (1)\vfill\eject
\write-1{3}3 (2)\vfill\eject
%
\FindPrimes
\bye

-
Perhaps there is a more intelligent manner using TeX arithmetic to test if some number is a multiple of another one: as dividing and the multiplying seems quite waste, the first division could well have produced internally the remainder. –  jfbu Jan 30 '13 at 10:43