Return to Question

Remark: Marvin Minsky talked about 26 variables, a-z, but of course the number of variables is arbitrary. Of course, a program that attempts the maximal output in n lines should have less than $\frac n2\ $ lines.

Remark: Marvin Minsky talked about 26 variables, a-z, but of course the number of variables is arbitrary. Of course, a program that attempts the maximal output in n lines should have less than $\frac n2\ $ variables.

==================

Acknowledgment I'd like to thank Greg Kuperberg for admitting the topic of Minsky programming language (and the whole topic) at sci.math.research, when he was the moderator of that group in the year 1993.

Remark: Marvin Minsky talked about 26 variables, a-z, but of course the number of variables is arbitrary. Of course, a program that attempts the maximal output in n lines should have less than $\frac n2\ $ lines.

==================

Acknowledgment I'd like to thank Greg Kuperberg for admitting the topic of Minsky programming language (and the whole topic) at sci.math.research, when he was the moderator of that group in the year 1993.

GENERAL REMARKS

Every computing method poses the challenge of finding a better method, or at least better for large parameters -- here, the number of lines may serve as the critical parameter. But the new method may run into its own obstructions that the next method may overcome.

Thus, in the case of Minsky programs, the simple method gives $\ S(n)=n\ $ output value in $\ n\ $ lines. The next method, that of a single multiplication "T", improves on the simple method as shown above but only for the number of lines at least 8. Thus, perhaps this is the first critical parameter.

Then, number of lines 11 is the next barrier -- but implementing two multiplications in the same program is not effective at all. It does better than the single multiplication but for values that are already large enough for other methods to do better. In particular, implementing the two multiplications method is too poor for the 11-line challenge, and later too, it will never be a champion. The overhead for double multiplication is 4 (it is 2 for the single multiplication). Thus, there is never a good time for this double multiplication method.

Open Problem: What is the maximal maximal output of an 11-line Minsky program? (And could you prove that the output of that program is maximal among all 11-line Minsky programs).

My own result is: maximal output = 28.

(If you can obtain $\ >20\ $ then it's already pretty good.)

The simplest Marvin Minsky programs look like this (explicit line labels added for the sake of the future readability):

$$ 01\!:\quad a+\!+ $$ $$ 02\!:\quad a+\!+ $$ $$ 03\!:\quad a+\!+ $$

That's the whole program. All variables of Minsky programs are initialized to 0. Thus the given program has maximal output a $=3$. And an n-line simple program consisting only of a++ instructions has output $\,\ S(n)=n$.

The Minsky programs' universe consists of the non-negative integers. The following program illustrates all three types of Minsky instructions (and there are no other types):

$$ 01\!:\quad b+\!+ $$ $$ 02\!:\quad b+\!+ $$ $$ 03\!:\quad b+\!+ $$ $$ 04\!:\quad b-\!- $$ $$ 05\!:\quad a+\!+ $$ $$ 06\!:\quad a+\!+ $$ $$ 07\!:\quad a+\!+ $$ $$ \quad\ \ 08\!:\quad \text{if}\,(a)\quad 04 $$ Thus, $$ x-\!-\quad \Leftarrow:\Rightarrow \quad x = max(0\ \ x\!\!-\!\!1) $$ When the current value of a variable is positive then the if-instruction redirects the execution to the line labeled as at the end of this if instruction, here to label 04. Thus, this program performs multiplication $3\cdot3,\ $ and it ends up with maximal output $\ a=9.\ $ The highest output that this times $\times\ $ multiplication method gets is $$ T(n)\ := \left\lfloor\frac {n-2}2\right\rfloor\cdot \left\lceil\frac {n-2}2\right\rceil $$ where $\ n\ $ is the number of the lines of the program. That's why getting more than 20 from 11 lines is already non-obvious to the public out there (if there were any public).

==================

The still yet missing explanations:

A valid program must end in a finite time. It ends by exiting through its end line.

After the execution of the program is done, the maximal value of the variables after the program is finished is the maximal value of the program.

In the above multiplication example, the whole output or the final output state is a=9 and b=0. Thus, the maximal output is 9.

==================

I'll be willing to answer any questions (at my best).

Acknowledgment I'd like to thank Greg Kuperberg for admitting the topic of Minsky programming language (and the whole topic) at sci.math.research, when he was the moderator of that group in the year 1993.

Open Problem: What is the maximal maximal output of an 11-line Minsky program? (And could you prove that the output of that program is maximal among all 11-line Minsky programs).

My own result is: maximal output = 28.

(If you can obtain $\ >20\ $ then it's already pretty good.)

The simplest Marvin Minsky programs look like this (explicit line labels added for the sake of the future readability):

$$ 01\!:\quad a+\!+ $$ $$ 02\!:\quad a+\!+ $$ $$ 03\!:\quad a+\!+ $$

That's the whole program. All variables of Minsky programs are initialized to 0. Thus the given program has maximal output a $=3$. And an n-line simple program consisting only of a++ instructions has output $\,\ S(n)=n$.

The Minsky programs' universe consists of the non-negative integers. The following program illustrates all three types of Minsky instructions (and there are no other types):

$$ 01\!:\quad b+\!+ $$ $$ 02\!:\quad b+\!+ $$ $$ 03\!:\quad b+\!+ $$ $$ 04\!:\quad b-\!- $$ $$ 05\!:\quad a+\!+ $$ $$ 06\!:\quad a+\!+ $$ $$ 07\!:\quad a+\!+ $$ $$ \quad\ \ 08\!:\quad \text{if}\,(b)\quad 04 $$ Thus, $$ x-\!-\quad \Leftarrow:\Rightarrow \quad x = max(0\ \ x\!\!-\!\!1) $$ When the current value of a variable is positive then the if-instruction redirects the execution to the line labeled as at the end of this if instruction, here to label 04. Thus, this program performs multiplication $3\cdot3,\ $ and it ends up with maximal output $\ a=9.\ $ The highest output that this times $\times\ $ multiplication method gets is $$ T(n)\ := \left\lfloor\frac {n-2}2\right\rfloor\cdot \left\lceil\frac {n-2}2\right\rceil $$ where $\ n\ $ is the number of the lines of the program. That's why getting more than 20 from 11 lines is already non-obvious to the public out there (if there were any public).

==================

The still yet missing explanations:

A valid program must end in a finite time. It ends by exiting through its end line.

After the execution of the program is done, the maximal value of the variables after the program is finished is the maximal value of the program.

In the above multiplication example, the whole output or the final output state is a=9 and b=0. Thus, the maximal output is 9.

==================

I'll be willing to answer any questions (at my best).

Acknowledgment I'd like to thank Greg Kuperberg for admitting the topic of Minsky programming language (and the whole topic) at sci.math.research, when he was the moderator of that group in the year 1993.