5
$\begingroup$

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)\ $?

$\endgroup$
9
  • $\begingroup$ I don't understand your explanation of the "goto". What is the role of the variable x? $\endgroup$ Sep 30, 2013 at 19:36
  • $\begingroup$ $M(n)$ is sufficiently similar to the busy beaver function that I’d expect it not to be bounded above by any computable function. $\endgroup$ Sep 30, 2013 at 20:08
  • $\begingroup$ @JamesCranch: This is most likely intended to be a conditional instruction: go to $nn$ if $x$ is nonzero (or maybe if it is zero, but the sort of C-like syntax rather suggests the first reading). What I am puzzled by is why x-- results in $\max\{x-1,1\}$ rather than $\max\{x-1,0\}$. Is this really intended? I believe this would actually make the model Turing-incomplete. $\endgroup$ Sep 30, 2013 at 20:18
  • 1
    $\begingroup$ So is the 1 intended or not? This makes for two dramatically different questions, you should explicitly clarify it. $\endgroup$ Sep 30, 2013 at 20:30
  • 1
    $\begingroup$ How does that answer my question on the definition of x--? $\endgroup$ Sep 30, 2013 at 20:35

2 Answers 2

3
$\begingroup$

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. 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$.

$\endgroup$
4
  • $\begingroup$ Will Orrick and I are interested in a similar question regarding absolute determinant values of 0-1 matrices. Given n > 1, what is the smallest positive integer d that is NOT the determinant (over the integers) of an n-by-n matrix whose entries are 0 or 1? Can you use something similar to show that d is $\Omega(n^{cn})$ for some constant $c$? (I can do better than $2^n$, but not much better.) Gerhard "Binary Minds Want To Know" Paseman, 2013.10.01 $\endgroup$ Oct 1, 2013 at 17:31
  • $\begingroup$ @Gerhard: This is an interesting question. I don’t see how to do it at the moment, but it might be worth looking at. $\endgroup$ Oct 1, 2013 at 19:31
  • $\begingroup$ @Gerhard's problem associates to me with the metric spaces and systems of linear diophantine equations. On the other hand I'd like to see its association with the "systematic computations". What is it? :-) $\endgroup$ Oct 2, 2013 at 14:41
  • $\begingroup$ @Wlodzimierz: Well, computation can be encoded in all kinds of finite combinatorial structures. 0–1 matrices (= directed graphs, essentially) are definitely of that sort. $\endgroup$ Oct 2, 2013 at 17:19
0
$\begingroup$

@Emil Jeřábek, thank you for your nice answer.

This question is mine--there is no need for anybody to tip me (upvote) for my answer here (bar owners don't get tips).

It's convenient to note, that any output a[0] value of any $k$-instruction program can be obtained like this for any $n$-instruction program whenever $\ 1\le k\le n$.   Indeed, to obtain the longer program first write $\ d:=n-k\ $ instructions   a[0]--. Then copy the shorter program but increase the target line numbers of the goto instructions by $\ d$.

Now let me slightly sharpen the upper bound on $\ M(n)$.   It is given by

$$ M(n)\ \le\ n\cdot n!\cdot (n+1)^n $$

Indeed,   let $\ \pi\ $ be an arbitrary $n$-instruction program. First let's prepend it by instruction   a[0]--,   and let's increase all target goto line numbers by $\ 1$.   We get a program $\ pi'$.

Next we obtain a program $\ p''$,  which doesn't differ from $\ \pi'\ $ but for a consistent renumbering of the variables. Let's assume (induction) that we have renumbered all variables of $\ \pi'\ $ which have appeared in lines numbered $\ 0\ldots J-1$,   and they have a new index in $\ \pi''\ $ (for $\ J=1\ $ the variable   a[0]   from $\ \pi'\ $ still stays   a[0]   in $\ \pi''$).   Consider line $\ J\ $ of $\ \pi'$.   If there is no variable in line $\ J\ $ of $\ \pi'\ $ which didn't show up in lines $\ 0\ldots J-1\ $ then there is nothing to do at this stage of induction. But if there is a new variable like this (in $\ \pi'$)   then rename it in $\ \pi''\ $ as variable a[J] (for the sake of elegance variables may jump). Of course also all future appearances of that variable in $\ \pi'\ $ will appear as a[J] in $\ \pi''\ $ respectively. End of induction.

Thus

$$ v\ \le\ t $$

for every appearance of variable   a[v]   in any line numbered   t   of program $\ \pi''\ $ (and the total number of variable is at the most   n,   which should be taken into account by the last line program).   This proves, with just an extra glance, the upper bound presented above.

REMARK   Instructions   x? L   are not allowed (by my definition in the Question) when   L   is the line number of the given instruction--there is no need for such instructions.

$\endgroup$
4
  • $\begingroup$ Some variations of the above proof are possible. One could consider just n-instruction proofs, and with an arbitrary output but it would have to be indicated as the output. The enumeration of the variables would be similar: $v\lt t$ whenever the variable index v would be less or equal the line number t. (The bound would be the same). $\endgroup$ Oct 3, 2013 at 5:15
  • 1
    $\begingroup$ The easy way to avoid tipping is to make the answer community wiki. $\endgroup$ Oct 3, 2013 at 14:32
  • 1
    $\begingroup$ Your argument saves a factor roughly $e^n$, but the bound is still $M(n)\le n^{(2-o(1))n}$. I didn’t bother explicitly optimizing constants in the argument above, but using the proof of Lupanov’s theorem such as in www2.cs.uni-paderborn.de/cs/ag-madh/WWW/Teaching/2005WS/… and adopting it directly for SL instead of going through circuit simulation, one can actually push it to $M(n)\ge n^{(1-o(1))n}$. So, the constant in the exponent is between 1 and 2. It's not clear to me what should be the right value. $\endgroup$ Oct 3, 2013 at 15:33
  • $\begingroup$ BTW, you can get a slightly better upper bound (but still with exponent 2) as follows. For any $0<v\le n$, there are $\le((n+1)v)^n$ programs using $n$ lines and $v$ variables, assuming these variables are $a_0,\dots,a_{v-1}$. However, any permutation of variable labels (except 0) yields a different program with the same exit value, hence such programs can output only $((n+1)v)^n/(v-1)!$ different integers. This expression is maximized when $n\sim v\log v$, in which case Stirling’s approximation yields $M(n)\le\left(\frac{n^2}{(e-o(1))\log n}\right)^n$. (All $\log$’s are natural here.) $\endgroup$ Oct 3, 2013 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.