The following somewhat popular simple computer language was enjoyed on sci.math, sci.math.research, pl.sci.matematyka, and perhaps before and after at several places (I wish I knew it's exact history). Call this language   SL.


An SL-program is a finite sequence of lines, enumerated from   $0$   to   $n-1$,   where   $n=1\ 2\ \ldots\ $ is an arbitrary natural number.


The language has an infinite array of unsigned (:-) integer variables $\ a[0]\ a[1]\ \ldots $, initialized to $0$ at the start, and it admits just three types of instruction: a decrement, an increment, and *go to*, or formally:


* x--
* x++
* x? nn


where   x   is any variable   a[n];   x--   replaces the value of   x   by   max(x-1   0);   x++ replaces the value of x by x+1;   and the last type of an instruction redirects the program conditionally to the line number nn (different from the current line number) when   x > 0. The flow of the program would be natural from the beginning to the end except for the *goto* instructions. A correct program would exit through the last instruction (when it was not successfully redirected back anymore).


Each time the traditional challenge consisted of writing a 23-line program which would achieve a maximal value of variable   a[0]   on the program's exit. (The number of variables was assumed to be only 26: $\ a\ldots z\ $--just 23 would suffice in the given case).


Given any fixed number $\ n\ $ of program lines, instead of computing the maximal value of a[0] on exit, I'd like to ask about the maximal number $\ M(n)\ $ such that:


* variable   a[0]   cannot obtain value $\ M(n)+1\ $ on exit;
* every value $\ 0\ \ldots\ M(n)\ $ of   a[0]   can be obtained on exit (by the respective $n$-line programs).


Do you see any approximate lower and upper bounds for $\ M(n)\ $?



A simple language and systematic computations
I claim that $M(n)=n^{\Theta(n)}$.


The upper bound is easy: we can assume without loss of generality that an $n$-line program only uses variables $a\_0,\dots,a\_{n-1}$, hence there are only $n^2+2n$ possible instructions, and $(n^2+2n)^n$ programs. Thus, one of the numbers $0,\dots,(n^2+2n)^n$ cannot occur as the exit value of such a program, i.e.,
$$M(n)<(n^2+2n)^n=O(n^{2n}).$$
Now, for the lower bound. Note that $M(n)=n^{\Omega(n)}=2^{\Omega(n\log n)}$ can be equivalently restated as saying that every $m$-bit integer can be computed as the exit value of a program with $O(m/\log m)$ lines, so this is what we need to show.


First, it is easy to see that every such number can be computed by a program with $5m$ or so lines (leading to the bound $M(n)\ge2^{n/5}$): the 4-line program snippet
\begin{align\*}
\text{loop:}&a\_0{-}-\\&a\_1{+}+\\&a\_1{+}+\\&a\_0?\text{ loop}
\end{align\*}
computes $a\_1:=2a\_0$ and clears $a\_0$ (provided initially $a\_0>0=a\_1$), and with one more increment, we can also do $a\_1:=2a\_0+1$ in 5 lines. By chaining $m$ such snippets (alternating between $a\_0$ and $a\_1$), we can produce any $m$-bit number.


For $O(m/\log m)$ lines, we have to be more sophisticated. Assume w.l.o.g. that $m=2^k$ is a power of $2$. Then an $m$-bit number can be identified with the truth table of a Boolean function $f\colon\{0,1\}^k\to\{0,1\}$.


Such Boolean functions can be computed by [Boolean circuits](http://en.wikipedia.org/wiki/Boolean_circuit). It will be convenient to represent here circuits as straight-line programs: a circuit $C$ of size $s>k$ computes $s$ Boolean values $a\_1,\dots,a\_s$ where $a\_1,\dots,a\_k$ are initialized to the $k$ input bits of $f$, and for each $k<i\le s$, we have an instruction of one of the forms
\begin{align\*}
a\_i&:=a\_j\land a\_k,\\
a\_i&:=a\_j\lor a\_k,\\
a\_i&:=\neg a\_j,
\end{align\*}
where $j,k<i$. The final value of $a\_s$ is the output of $f$.


We can compute the number whose binary representation is the truth table of $f$ by an SL-program with the following structure:
\begin{align\*}
\text{loop:}&\textit{/\* assume $a\_1,\dots,a\_k$ hold an intended input of $f$: \*/}\\
&\text{simulate the computation of $C$}\\
&\text{double $a\_0$}\\
&\text{if $a\_s>0$, $a\_0{+}+$}\\
&\textit{/\* increment $a\_1,\dots,a\_k$ as a $k$-bit binary integer: \*/}\\
&\text{if $a\_1=0$: $a\_1:=1$, go to loop}\\
&a\_1:=0\\
&\text{if $a\_2=0$: $a\_2:=1$, go to loop}\\
&a\_2:=0\\
&\dots\\
&\text{if $a\_k=0$: $a\_k:=1$, go to loop}\\
&\textit{/\* halt \*/}
\end{align\*}
It is easy to see that each instruction of $C$, as well as each of the remaining lines of the pseudocode above, can be implemented with a constant number of SL instructions, hence the total length of the program is $O(s)$.


Now, the crucial point is that by a nontrivial result in circuit complexity going back to Shannon, every Boolean function in $k$ variables can be computed by a circuit of size $s=(1+o(1))2^k/k$ (and this bound is tight for the vast majority of Boolean functions). Thus, every number with $m=2^k$ bits can be output by an SL-program of length $O(2^k/k)=O(m/\log m)$, as claimed.


EDIT: One way of proving the weaker (but sufficient above) bound that every $f\colon\{0,1\}^k\to\{0,1\}$ is computable by a circuit of size $O(2^k/k)$ is as follows. First, by recursively expanding
$$\tag{$\*$}f(x\_1,\dots,x\_k)=(x\_k\land f(x\_1,\dots,x\_{k-1},1))\lor(\neg x\_k\land f(x\_1,\dots,x\_{k-1},0)),$$
we see that $f$ has a circuit of size $2k+3(2^k-1)$ or so. We can shorten it by observing that this circuit has many redundancies: there are nodes computing the function $g(x\_1,\dots,x\_d)=f(x\_1,\dots,x\_d,a\_{d+1},\dots,a\_k)$ for each $d<k$ and $a\_{d+1},\dots,a\_k\in\{0,1\}$, and many of these functions actually coincide. We can exploit this by precomputing the values of all $2^{2^d}$ Boolean functions in variables $x\_1,\dots,x\_d$. This can be done by a circuit of size $2^{2^d}$: take the concatenation of arbitrary circuits computing all these functions, and remove redundant nodes computing a function that is also computed by another node earlier in the circuit. After this reduction, no two nodes in the circuit compute the same function, hence there are only $2^{2^d}$ nodes.


Now, if we apply the expansion $(\*)$ only until we reach functions in $d$ variables, and use the precomputed values for these, we obtain a circuit for $f$ of size
$$s=2(k-d)+3(2^{k-d}-1)+2^{2^d}.$$
Taking $d=\lfloor\log\_2(k-2\log\_2k)\rfloor$, we have
\begin{align\*}
2^{k-d}&\le\frac{2^{k+1}}{k-2\log\_2k}=(2+o(1))2^k/k,\\
2^{2^d}&\le2^k/k^2=o(2^k/k),
\end{align\*}
hence $s\le(6+o(1))2^k/k$.


