Laaarge numbers, Part I

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?

Leave a Reply

Your email address will not be published. Required fields are marked *