An Extremely Simple Programming Language

Question

After preparing for years, you go to the 51st Intergalactic Coding Olympiad. The moment the test starts, you flip over the question paper. To your surprise, it has only one question which involves... none of the programming languages that you studied.

The question describes a programming language called Easy, which can only do five things.

• It can set a variable to 0, creating it if it doesn't exist.
• It can increment a variable if the variable already exists.
• It can create a (possibly infinite) loop containing any set of instructions. Loops can be nested.
• It can break out of a loop if two specified variables are equal. When this type of statement is used nested loops, it only breaks the innermost loop.
• It can return a variable and stop the program.

The syntax is very similar to Java syntax. Each one of the above instructions counts as 1 instruction.

Here's an example Easy program (with 7 instructions) that returns 1, illustrating the syntax:

i = 0;
j = 0;
i++;
loop {
    j++;
    if (i == j) break;
}
return j;

The question has three parts:

• a) Write a program with at most 15 instructions that returns an integer greater than 20.

• b) Write a program with at most 20 instructions that returns an integer greater than 1000.

• c) Write a program with at most 25 instructions that returns an integer with a decimal representation that cannot fit in this universe.

Bonus: What is the largest number you can return on each part?

Note: The bonus question is well-defined and has a unique answer for each of the 3 cases (15, 20, 25 instructions). For details, see answer by will.octagon.gibson.

Note: Since some tame-looking Easy programs can return HUGE numbers, Easy is not run by directly running the code, but rather by scanning the code with a superintelligent coding AI and making it compute the value that is returned by figuring out what each code segment does.

Answer 1

First, define a macro for used as

for (i) {
  CODE
}

that takes a variable i and any lines of CODE. It expands to

i = 0;
loop {
  CODE
  if (i == x) break;
  i++;
}

which adds $4$ instructions to CODE. If CODE

maintains the invariant $x-i$, then for runs CODE for $x+1$ times.

Next, define a function $f_n(x)$ for $n\ge0$ as

for (i_1) {
  for (i_2) {
    ...
    for (i_n) {
      x++;
      i_1++;
      i_2++;
      ...
      i_n++;
    }
    ...
  }
}

which uses $5n+1$ instructions. Observe that

incrementing both $x$ and $i_k$ maintains each invariant $x-i_k$, so each $f_n$ runs $f_{n-1}$ for $x+1$ times.

Formally, $f_n$ is defined recursively as

$$f_n(x)=\begin{cases}x+1,&n=0\\f_{n-1}^{x+1}(x),&n\ge1\end{cases}.$$

For example,

$f_0$ increments $x$, so $f_1$ increments $x$ for $x+1$ times, giving$$f_1(x)=x+(x+1)=2x+1.$$

Finally, define the program $P_n$ as

x = 0;
x++;
x++;
f_n(x);
return x;

which uses $5n+5$ instructions and outputs $f_n(2)$.

$P_2$ uses $15$ instructions and outputs

$$f_2(2)=f_1^3(2)=f_1^2(5)=f_1(11)=23>20.$$

$P_3$ uses $20$ instructions and outputs

$$f_3(2)=f_2^3(2)=f_2^2(23)>f_2(2^{28})>2^{2^{28}}>(10^{80})^{10^6},$$which is approximately the number of atoms in the universe—to the power of one million.

$P_4$ uses $25$ instructions and outputs

$f_4(2)$, an extremely large number.

For illustration purposes, here are the three programs written in full.

$P_2$:

x = 0;
x++;
x++;
i = 0;
loop {
  j = 0;
  loop {
    x++;
    i++;
    j++;
    if (j == x) break;
    j++;
  }
  if (i == x) break;
  i++;
}
return x;

$P_3$:

x = 0;
x++;
x++;
i = 0;
loop {
  j = 0;
  loop {
    k = 0;
    loop {
      x++;
      i++;
      j++;
      k++;
      if (k == x) break;
      k++;
    }
    if (j == x) break;
    j++;
  }
  if (i == x) break;
  i++;
}
return x;

$P_4$:

x = 0;
x++;
x++;
i = 0;
loop {
  j = 0;
  loop {
    k = 0;
    loop {
      l = 0;
      loop {
        x++;
        i++;
        j++;
        k++;
        l++;
        if (l == x) break;
        l++;
      }
      if (k == x) break;
      k++;
    }
    if (j == x) break;
    j++;
  }
  if (i == x) break;
  i++;
}
return x;

Update: We can make a small optimization to $f_n$ by moving the first increment of $i_n$ after the $i_n=x$ test. This allows an extra iteration of the innermost loop, so our definition becomes

$$f_n(x)=\begin{cases}x+1,&n=0\\2x+2,&n=1\\f_{n-1}^{x+1}(x),&n\ge2\end{cases}.$$

Using this modified version of $f$, $P_2$ now outputs

$$f_2(2)=f_1^3(2)=f_1^2(6)=f_1(14)=30.$$

$P_3$ now outputs

$$f_3(2)=f_2^3(2)=f_2^2(30)=f_2(2^{36}-2)=2^{2^{36}+35}-2\approx100^{{10}^{10}}.$$The Googology Wiki calls this number guppythrong.

$P_4$ now outputs

$$\begin{align}f_4(2)&=f_3^3(2)\\&=f_3^2(2^{2^{36}+35}-2)\\&\approx f_3(2\uparrow\uparrow2^{2^{36}})\\&\approx2\uparrow\uparrow2\uparrow\uparrow2^{2^{36}}\\&\approx10\uparrow\uparrow10\uparrow\uparrow10\uparrow\uparrow3,\end{align}$$where $\uparrow\uparrow$ represents tetration using Knuth's up-arrow notation. The Googology Wiki calls this number trialogialogialogue.

Answer 2

Considering that the main stated puzzles have been solved, whole problem kinda transformed into free-form "busy beaver"-esk challenge/analysis...

Just to give some upper bounds on comprehensibility:

Here's a rudimentary 44-instruction program with unknown fate:

zero = 0
one = 1 // 2 instructions

count = 0
x = 7 // 8 instructions

loop
{
  count++

  temp = 0

  loop
  {
    flag_odd = 0
    if temp == x: break // detect if even
    temp++
    flag_odd++
    if temp == x: break // or odd
    temp++
  }
  // at this point temp == x

  temp2 = 0
  x = 0
  loop // even case
  {
    if flag_odd == one: break
    if temp2 == temp: break
    temp2 += 2 // 2 instructions
    x++
  }
  
  loop // odd case
  {
    if flag_odd == zero: break
    x++
    loop
    {
      if temp2 == temp: break
      temp2++
      x += 5 // 5 instructions
    }
    if zero == zero: break
  }

  if x == one: break
}
return count

it repeatedly applies "Collatz' 5n+1" function

$$ f(n) = \begin{cases}n/2, &n = 2k \\ 5n+1, &n=2k+1 \end{cases} $$

whose trajectory isn't known whether it comes down to 1 if starting value is 7 (5th term)

---

And here's 31-instruction program emulating anti-hydra

x = 0
big = 1
small = 0 // (big-small-1) := 0

loop
{
  temp = 0
  temp2 = 4

  small++
  loop
  {
    big += 3 // 3 instructions
    if temp == x: break // if x=2k: (big-small-1)+=2, temp2:=3k+4
    temp++; temp2++

    small += 3 // 3 instructions
    if temp == x: break // if x=2k+1: (big-small-1)-=1, temp2:=3k+5
    temp++; temp2 += 2
  }
 
  loop // x := temp2
  {
    if temp2 == x: break
    x++
  }

  if big == small: break
}
return big  // if (big-small-1) became -1: halt

it is a Collatz map

$$ \begin{cases}\text{Start} &\rightarrow (0,0)\\(2n,b) &\rightarrow (3n+4,b+2)\\ (2n+1,0) &\rightarrow \text{Halt} \\ (2n+1, b+1) &\rightarrow (3n+5, b) \end{cases} $$

that popped up in busy beaver investigations - and it is currently unknown whether it halts or not

Answer 3

Code for (a):

 a = 0;
 a++;               // (repeated x5)
 b = 0;
 loop{
   a++;             // (repeated x2)
   if(a==b) break;
   b++;             // (repeated x3)
 }
 return a;

The idea is

the loop repeatedly adds three to b, and two to a, so by the time they are equal a has been tripled. However, having a start at 5 means we'd only get to 15. But by putting the b++ lines after the if statement, we get two a++ lines "for free", and thus we can get to 21.

Answer 4

This code has exactly 15 instructions, and returns increasing powers of two, until infinity.

Here it is:

a = 0;
b = 0;
c = 0;
a++;
c++;
loop {
 loop {
  b++;
  c++;
  if (a == b) break;
 }
 loop {
  a++;
  if (a == c) break;
 }
 return c;
 b = 0;
}

Answer 5

This analysis is not an answer but is too long for a comment.

The bonus question asks, “What is the largest number you can return on each part?”

No matter how many instructions are allowed, I will show that the bonus question is well-defined in that there will be a unique largest positive integer $N$ that can be returned by some program.

I will analyze the 15-instruction case (the other cases are similar).

Since there are at most 15 instructions, there are at most 15 variables. Without loss of generality, name these variables a, b, c, … m, n, o.

Let’s now consider all the possible instructions that can be used to make up a program:

• It can set a variable to 0, creating it if it doesn't exist. (15 possibilities)
• It can increment a variable if the variable already exists. (15 possibilities)
• It can create a (possibly infinite) loop containing any set of instructions. Loops can be nested. (15 possibilities: Loop containing 0 instructions, Loop containing 1 instruction, … Loop containing 14 instructions)
• It can break out of a loop if two specified variables are equal. When this type of statement is used nested loops, it only breaks the innermost loop. (225 possibilities, 15 for first variable and 15 for second variable)
• It can return a variable and stop the program. (15 possibilities)

Some of the above possibilities are mutually exclusive or syntactically invalid but I only want to show that there are a finite number of essentially different programs.

There are at most $p=4 \times 15 + 225$ possible instructions we can use to build a program.

A program can have up to 15 instructions. Therefore the number of essentially different possible programs is at most $E=p^0 + p^1 + p^2 + \cdots + p^{15}$. Note although $E$ is very large, it is finite.

Even if all these $E$ programs returned an integer, there is only a finite number of possibilities for these returned values. Call the maximum of these values $N$. Then $N$ is the answer to the bonus question.

Answer 6

Too big for a comment, but I wanted to share this explicitly:

This language is Turing-complete, proved by emulation of Fractran

---

Fractran program is defined as a set of fractions $\left(\frac{x_1}{y_1},\frac{x_2}{y_2},..., \frac{x_n}{y_n}\right)$ and a starting value $S_0$

On each computation step you go through fractions, one by one, first to the last - and check if $S$ is divisible by $y_i$. If it is, you calculate next value of $S$: $S_{k+1} = S_k\times \frac{x_i}{y_i}$ and move on to the next step.

Optionally, if $S$ isn't divisible by any of the denominators - machine is considered to have halted with the last value of $S$.

If you want an intuition for why Fractran is Turing-complete - look at prime factorization: $2^{f_2}3^{f_3}5^{f_5}...$ - you have infinite number of "registers" - one per each prime number - and fractions detect which of them are empty and which should be added to

---

To emulate Fractran in Easy, we'll need to know that:

1: we can increase variable by any constant x += c by applying x++ c times
2: we can assign variable to any constant value x = c via x=0; x += c
3: we can assign one variable to another x = y via:

x = 0
loop
{
  if x == y : break
  x++
}

4: we can define Fractran_ministep(S,x,y) to be

temp = 0; temp2 = 0; S_new = 0
loop
{
  S_new += x
  loop
  {
    temp++; temp2++      // subtract from (S-temp)
    if temp == S: break  // until it runs out
    if temp2 == y: break // or until it was decreased by y
  }
  if temp == S: break    // if it ran out, temp2 := S%y (in [1;y] range)
  temp2 = 0              // if it didn't, reset y-counter
}
if temp2 == y: break // it's the correct fraction, S_new := S*x/y

(it breaks the loop it is in with the next value of $S$ in S_new, if the fraction is correct - and continues on, if it isn't)

5: And, finally, we can construct the whole emulation program as so:

S = S_0
loop
{
  loop
  {
    x = x_1; y = y_1
    Fractran_ministep(S,x,y)

    x = x_2; y = y_2
    Fractran_ministep(S,x,y)

    ...

    x = x_n; y = y_n
    Fractran_ministep(S,x,y)

    return S
  }
  S = S_new
}