What is the largest number you’ve come across? A million is a lot when you think of it as money. A billion is a lot when you think of it as operations to do on a computer. $10^{100}$ is a lot when compared to the number of atoms in the universe. $10^{2 000 000}$ is a loot of books. Still, each one of those numbers can be written out by a one and a moderate amount of zeroes. The *googolplex* $10^{(10^{100})}$ couldn’t be written out in a physical form any more (though in a digital one), and what it would count is unimaginably large. But again, it comes in a nice and compact form that we’ve just written down: $$10^{(10^{100})}$$

We want to get numbers larger than that. And not just a single one of them, but a whole function $f$ that takes a number and computes a large number out of it, growing extremely fast. For example

$$f(n) = 10^{10^{10^n}}$$

is growing quite fast, in fact we already get the googolplex as $f(2)$. We could now play the silly game and include larger and larger power towers, take factorials like

$$f(n) = n^{n^{n!}}$$

and so an. We will be looking for a concept of a fast-growing function that subsumes all of these.

# The *LOOP* language

The *LOOP* language is a very simple programming language. All of its variables do hold arbitrarily sized integers and are initialized to $0$. The only statements of the language are assignments with some arithmetic (+,-,*,/) like

```
x = x + 2*(y - z/2)
```

and loops like

```
loop n
<body>
end
```

The loop reads the value of `n`

*at the beginning* and runs its body exactly as many times (or not at all if the expression isn’t positive). It doesn’t care if we change the value of `n`

inside the loop. So the program

```
n = 5
loop n
n= 2*n
end
```

doubles `n`

five times, resulting in `n = 160`

.

Let’s convince ourselves that *LOOP* is surprisingly powerful: For example, we can simulate `if`

switches with loops. Instead of

```
if n == 5
spam
else
eggs
end
```

we write

```
loop n - 4
loop 6 - n
eq = 1
end
end
neq = 1
loop eq
spam
neq = 0
end
loop neq
eggs
end
```

We don’t care if the solution is efficient, we just care for a *LOOP* program that computes what we want.

**Brainteaser 1)** Can you write a *LOOP* program that tests if $n$ is prime?

**Brainteaser 2)** Can you write every *LOOP* program as one that only uses basic statements `var = var + 1`

, `var = var - 1`

and `loop var`

?

Let’s now use *LOOP* to generate large numbers. Surely, we can exponentiate

```
n = 10
loop 100
n = n * 10
end
```

and take factorials

```
n = 10
i = n - 1
loop n - 2
n = n * i
i = i - 1
end
```

and we can get our googolplex

```
k = 10
loop 100
k = k * 10
end
n = 10
loop k
n = n * 10
end
```

We can create incredibly large numbers by nesting loops in worse and worse ways

```
n = 10
loop 100
loop n
n = n*n
end
end
```

**Brainteaser 3)** Think of how large the output of this program is.

Sure, we have a program that generates an enormous number. What’s so special when we have programs that generate arbitrarily high numbers?

```
while true
n = n + 1
end
```

But that’s not a *LOOP* program. And we cannot write any *LOOP* program that does the same job. This is because

Every LOOP program terminates.

The instruction pointer will inevitably reach the end of the program, and it can only loop back a *fixed* number of times. There is no endless loop in *LOOP*. **Let that statement sink in!** It means the length of a program somehow bounds how long it can run! Bigger numbers require larger programs. Still, already a small program can run extremely long. We want to measure how long.

If we take `n`

to be our dedicated output variable, every loop program will generate a well-defined number. There are only finitely many sourcecodes of length at most `k`

and even fewer of these are syntactically valid *LOOP* programs. We can therefore define

$$f(k) = \text{ maximum output of a LOOP program of length at most $k$. }$$

**Brainteaser 4)** Convince yourself that f grows faster than any of the “large” functions we looked at before.

**Brainteaser 5)** Can there be a *LOOP* program that, given $k$, computes $f(k)$?

**Brainteaser 6)** Can you implement a quick parser/interpreter for *LOOP*?

**Brainteaser 7)** How would you implement procedures in *LOOP*? Is recursion possible?