Using Opus Magnum computers.. irrationally

This is going to be a short post about a design from a few months ago. Because the 2022 Opus Magnum tournament was still ongoing, I didn’t do much writing during those months.

It began with a question. “Can rate be nonrational?” This set off a few brilliant ideas and designs, using the principles of computation to achieve this goal.

Throughput Revisited

In my very first post to this blog, I discussed throughput as an alternative metric by which Opus Magnum solutions can be measured. Rather than counting to 6 outputs, your solution races to infinity, aiming only to have the most outputs per unit time in steady state. I gave the following caveat about its measurement:

There is a clear problem though. Throughput can’t be quickly checked by the game, in the same way as cost or cycles or area. Opus Magnum is Turing Complete, and people have built computers in the game (I will make a post on that one some other time). When you require a solution to run forever, you end up with examples reminiscent of the Halting Problem. By replacing 6 with infinity, we moved toward scoring systems which require mathematical proof. Fortunately, many solutions are simple cases where the machine settles into a steady state. If there are identical board contents before and after the instruction tape has looped, the proof is trivial.

Me, brushing an entire world of possibilities under the rug

It’s time to open this can of worms.

The Easy Part

Let’s completely forget about chasing perfection, and just evaluate a “normal” Opus Magnum solution. In the machine below, two arms build outputs from the inputs, and settle into a loop.

On cycle 22, the machine drops an output. On cycle 23, the small arm starts over with the instructions it performed on cycle 1. Shortly afterward, the piston starts its instructions over as well. It began slightly later than the small arm, starting on cycle 3 instead. It performs its first instruction again on cycle 25.

This machine loops, with a 22 cycle loop in total. By luck, it also drops its output on 22, so every output will happen on a cycle which is a multiple of 22. Without actually running this solution to cycle 22 million, we can be confident it will drop its millionth output exactly then.

Different values of T

Back in my instructions post, we defined T, which determines how many outputs a solve produces each time the tape loops. The easy solution above is 1T. For that reason, there’s a specific drop instruction on the piston, which will always deliver an output. Every single time that instruction executes, the product count goes up by one.

With a 2T solution, there are two such instructions in the solution, possibly on different arms. And so the throughput would be two products, divided by the number of instructions in the tape. For example, here is 2 outputs per 7 cycles.

With a fractional T solution, as is common in quite a few of the trackless instruction designs, there are drop instructions that may-or-may-not drop an output. A simple example would be the Hair Product from that post.

The product rotates through 4 possible amounts of completion, on a 7 cycle loop. Its throughput is pretty easy to calculate, one product per 4 * 7 = 28 cycles. Of course, it’s easy because we can find where it loops.

Algorithmic detection

There are a lot of tools made by the community to work with Opus Magnum solutions, and the list keeps growing. One particularly prolific author, panic, built a throughput detector. He added it to the bot that tracks the best known solutions, so that people could finally submit to metrics involving throughput.

To keep up with the “lower is better” idea present in all other metrics, this bot actually computes the inverse of throughput, which we named “rate”. The rate of a solution making an output every 28 cycles, is 28. The rate of a solution making two outputs per 7 cycles, is 3.5.

To figure out the rate value of a solution, panic’s detector starts with a buffer of 100 tiles in every direction around the starting machinery. The world state within this region, will eventually loop (it has to, more on that later). When it does loop, returning to some state that it has been in before, the detector counts the number of outputs before and after looping. It counts the number of cycles before and after looping. Take differences, and then take their ratio. Easy rate calculation.

The reason for needing to ignore things outside of a certain radius, is that some solutions push waste polymers out to infinity. See below for an example.

The big question

We described the rate finding algorithm as the ratio between two counted quantities, one of products and one of cycles. Counting things gives integers. Taking the ratio between two numbers gives a rational number. But in a community of mad scientists who enjoy pushing the limits, 12345ieee asked the following question:

And people took interest:

Let’s dive deeper.

Irrational Throughput

An irrational number cannot be expressed as a fraction with integers in the numerator and denominator. There are loads of famous irrational numbers like pi, which come up naturally when asking math questions. But it seems like anything producing an irrational throughput in Opus Magnum, would need to be rather unnatural.

What’s in a solve

Any given solution has a finite number of instructions, a finite number of arms, and a finite number of tracks. This has a few implications:

• There is a first and last instruction, so there is a finite loop length
• Arms, including those on track, can be in finitely many positions and orientations
• Because the product of finite numbers is finite, after enough times through the instruction tape, you are guaranteed to have arms in all the same places they have been before, while they execute the same instructions

In other words, any solution file you can make, has to have all its machinery loop. Any individual drop instruction that could deliver an output, ultimately happens at a regular cadence. The only control we have, is over the T value. The T value is rational if and only if the rate and throughput are rational.

The atoms themselves

To avoid falling into a rational pattern, we need the state of the atoms on the board to be new each time the machinery loops. To handle the differences in atomic state, we need programming with some conditionals. This is exactly what we talked about with building a computer. See the NOT gate below for a refresher.

Atoms add a lot more possible ways to avoid looping, for a while. But to run forever without looping, we require an infinite set of board states. We need to take full advantage of the infinite space we are given.

Embrace infinity

We already saw a throughput solution with eventually-infinite area, with Viper Antidote. But that solution didn’t do anything tricky with its waste atoms. If you push an atom off to infinity and never touch it again, it’s just as practically useless as an atom that got dropped into a disposal. We have a non-looping board state due to moving endpoints of waste sticks, but every other part of the solution loops.

Our ultimate goal is that the behavior of the output glyph is fully non-looping. So any difference between two of the infinitely many board states, has to cause a difference in some future time that an output drops. Even if that difference is millions of tiles away from the output glyph.

It turns out, necessary features of irrational throughput are:

• The machine creates arbitrarily long molecules
• At least some atoms from those molecules make the entire journey back to the arms
• Using computational logic on those atoms, the solution gets an irrational T value

Brainstorming

Clearly the nicest thing I could do for my readers would be to show an example of a machine that pulls this feat off. But I’m also greedily telling the story of the pioneers who blazed that trail, and those pioneers did not have an example to study. So I’ll leave you in the dark for a couple more sections.

What is the simplest irrational number to compute? Pi is important, but not simple. Square roots can be rather simple, since there are algorithms that converge quickly to them. A few people bounced ideas around regarding the square root of 3, since it has a lot of connections to the hexagonal grid in the game. The distance from a tile to the next tile vertical from it, is square root of 3 units. Unfortunately, you can’t move by one tile vertically, only diagonally, and in that axis the distance is the far less irrational number, 2.

My idea regarded the golden ratio. Famously, the golden ratio shows up as the limiting ratio of successive Fibonacci numbers, the sequence 1, 1, 2, 3, 5, 8, 13 coming from adding two latest numbers to get the next. Technically the golden ratio is related to the square root of 5, but the Fibonacci connection was much more useful for me to come up with an idea.

Fibonacci Sequence counter

If we made a machine that output for one tape loop, and then didn’t output for 1 tape loop, then output for 2 tape loops, then didn’t output for 3 tape loops, output for 5, didn’t for 8, etc… Would it have irrational throughput? This sounded possible, since you could have one bit of information controlling whether to output or not, and flip that bit after counting the next Fibonacci number.

Unfortunately, the throughput of this idea is undefined!

Since throughput is a mathematical property involving a limit, you only have a throughput when the limit exists. My idea actually bounced back and forth between two irrational values. After a long spell of outputting, it would come close to the higher value. Then after a longer spell of not outputting, it would have fallen back to the lower value.

In more formal terms, the throughput of this hypothetical Fibonacci bit flip solve had a lim sup and a lim inf. Both of them were irrational, and they were actually a factor of the golden ratio apart from each other. But since lim sup and lim inf were not equal, the solution did not have an actual irrational throughput, or any throughput at all.

Bambi to the rescue

After a couple of hours of brainstorming in Discord, the topic died down a little. People were thinking about their own ideas and seeing whether they could get them to work, but nobody was sharing anything.

Then a player who goes by Bambi broke the silence, with a complete solution.

If you frequent my blog, you will have seen plenty of solutions in the past where you want to go “ooh” and “ahh” but the only thing you can manage is “..huh??” This is one of those. So it bears some explanation!

The machine

Bambi had made a custom puzzle with two fire inputs and one fire output. Since the puzzle itself is trivial, the machinery can be devoted entirely to conditional logic.

Two of the arms are useful only once. Both of them are length 2 non-piston arms, and they help set up the steady state. So the computation is being done by the other three. The hex-arm in the bottom left, and the two pistons.

The hex arm has the drop which may or may not deliver an output, after its second rotate counterclockwise. First, the fire spends a cycle on a triplex bonder. During that cycle, the top piston determines whether that fire gets to be output. If the top piston is carrying salt, it won’t bond to the fire below, and the hex arm will output that fire. If the top piston is carrying fire, it will bond, and no output gets made.

The two pistons work together to give the top piston something to grab every single time. But the question of whether it is fire or salt, is the source of nonlooping behavior.

Fibonacci numbers

The top piston grabs a stick of atoms, and unbonds one. Let’s count how long the stick is each time it does this.

1, 2, 1, 3, 2, 1, 5, 4, 3, 2, 1, 8, 7, 6, 5, 4, 3, 2, 1, 13, 12…

If the stick has multiple atoms, the next time is just one fewer. But when it gets to one, the lower arm’s programming leads to a different outcome, and a new stick takes its place. The lengths of those new sticks are 1, 2, 3, 5, 8, 13, 21, 34, 55.. This may be a familiar sequence.

The top stick grows by either one or two atoms, for every atom removed from the bottom stick. Using the triplex bonder, it obtains the maybe-second atom whenever it grabs fire. This leads to the replacement salt->fire, and fire->salt+fire. If the stick length is a Fibonacci number, and the number of fire in it is the next Fibonacci number down, that would lead to perfect growth according to the Fibonacci sequence. All that is required to get it started is a stick of length 1 containing 1 fire.

In essence, the stick holds onto a record of what was just output, and what will be output during the next pass. Dividing it into salt+fire (failed output), and lone fire (successful output), tells about the past. Dividing it directly into salt and fire, tells about future outputs. Information is reused from arbitrarily far away, just as we determined it needs to be.

Does the limit actually exist this time?

I think so

Bambi claimed that the throughput is 1/(16φ²), where φ is the golden ratio. This can also be written as an average of 3 – √5 outputs per 32 cycles. Certainly an irrational number if true.

At a fully rigorous level, we would provide some N-ɛ proof saying that “for any ɛ, we can find a value of N such that after N cycles, the total outputs / total cycles is always within ɛ of the true throughput.” I don’t really want to do that in this blog though.

Instead, panic quickly built out a tool to graph total cycles / total outputs out to a million simulated cycles. It looked like this:

The fact that both the top and bottom of the envelope are growing closer to the red line (theory value), is encouraging. Maybe there’s something to worry about, from how the top border seems to be leveling off a fair bit above the line. I invite any enterprising mathematician to try to rigorously prove the behavior of this machine. We know the number of outputs and the number of cycles at the end of each stick, we just need to know that it can’t deviate too badly towards too many or too few outputs, over the course of processing a stick.

This graph left us happy enough that the rate converged.

Simplification

Bambi’s solution uses both triplex and duplication. It turns out, no campaign puzzle gives you both. I was interested in simplifying the concept into something that could be put into practice on just about any puzzle. So I made the following Face Powder solution. This one has throughput 3 – √5 outputs per 26 cycles, under the same assumed convergence as before.

In essence this is the exact same solution, but with different conditions and geometry. What was a stick of salt and fire, is now a stick of single and double earths. The single earth is replaced by single+double on the next stick. The double earth makes an output and is replaced by a single earth on the next stick. Every conditional required to do this, is possible using only the output, bonders and unbonders. Because this is face powder, I had to add one calcifier there right before output.

As a nice added bonus, every atom is eventually output. Singlets become doublets on the next round trip, which get output. The hex arm pulls other atoms back into circulation if they were not used up by the output check.

Bambi’s Fibonacci design, and its derived solutions like the one above, remain to date the only examples of a machine with irrational throughput. It’s a very elegant solution to the combination of requirements brainstormed above.

Maybe we’ll make a solution someday with average one output per pi cycles. That would be neat.