3. Subroutines and Rube Goldberg
Suppose you want to accomplish a task. You could write a short program in Python. Or you could start a new Minecraft world, build a redstone computer, and program it to perform the task.
Some tasks are more suited for this in general, but that’s not important right now. You can imagine the task of computing the first 3 digits of pi, if it helps you visualize this.
The causal structure of the program is the same whether you implement it in Python, Minecraft, or a GoL contraption. The ease of understanding it, however, is not. The ease of reusing it is likewise different.
There’s an infinite number of obscure ways of running some program. Some are shorter than others. More to the point, some are written in the same language, and some have a bunch of weird scaffolding around them.
So I want to coin some terms. “Direct embedding” I will use for the concept of a subroutine call. “Rube Goldberg embedding” I will use for the concept of running something that itself is Turing Complete and happens to be set up to run your algorithm.
So, computing some digits of pi in python and then using a library function to convert that to a string? Direct embedding. Starting up a Minecraft universe, with a redstone computer, and using that to do the conversion to a string? Rube Goldberg embedding.
In one sense, this is a distinction only a human could care about. They do the same thing, right? But in another sense, if you evaluate program length, direct embedding is almost always much shorter. That is, to do a Rube Goldberg embedding, you’re typically paying the penalty of logic that computes a bunch of stuff that you may not care about (creepers in your redstone computer). That is, len(ToString<PiDigits<5>>) is much less than len(MinecraftComputer<ToString><PiDigits<5>>), where <> indicate a parameterization of a program.
Are there exceptions to this length rule? It seems that there are. Imagine you want to compress the 30th row of rule 30. Since it is quite random, a program that directly encodes this may take more space than a program that just runs rule 30 for 30 steps. We could call this a “subtle” Rube Goldberg embedding, if we wanted to classify them more specifically. Subtle because they’re difficult to spot. A subtle Rube Goldberg encoding typically computes a lot more than what you’re looking for: it’s trivial to stop at row 30, for example, but suppose we wanted the 4328th through 4345th bits of the 10000th row? Now it may be more efficient again to just encode those 17 bits directly, rather than the numbers 10000, 4328, and 4345 in addition to the rule 30 machinery. In other words, you pay a location penalty to find the output you want in the middle of all the other stuff the program prints.
An “obvious” Rube Goldberg embedding, in contrast, is one where there’s a big chunk of the program (e.g. MinecraftComputer<>) that can be removed without changing the output. These are straightforward to construct, but aren’t generally terribly useful.
These distinctions will become important as we start to consider the problem of examining arbitrary programs. Determining whether program X is a subtle Rube Goldberg embedding of program Y is a topic we will take up in the future.
