Optimizing arbitrary expressions with a linear number of queries to a Logical Induction Oracle (Cartoon Guide)

This is Logical Induction, or LI for short.

We can ask LI any maths question that has a number as an answer. If we ask it a question that is too tricky, it will have a good guess. On average, LI is neither too high or too low. Here we see that it has no idea what the $10^{100}$ th digit of $π$ is, except that it is a digit, so it averages all the digits from 0 to 9 together.

A green box indicates a question has a blank space in it. A green box around a binary string means the question you get when you put that binary string into the blank space.

For example, here are some green boxes you could use.

It can be an easy question or a hard question. We can pick any question we like that has a blank space in it.

LI will take in a string in a green box, and try its best to output a number.

Now suppose that some strings of 0′s and 1′s are better than others for some task we are trying to do. The green box represents a question asking how good the string is.

Maybe the string encodes the design of an engine, and the green box represents the question of how efficient that design is.

We could find the best string we can by asking LI about every possible string.

Unfortunately, there are a lot of possible strings, so this approach would be quite slow, even if LI itself was fast.

Is there a quicker way?

We can ask LI questions about itself.

This cloud represents a question about the best value that LI can figure out how to get from a string of bits that starts with $x$ , and then contains another $n$ bits.

We define it like this

Note that the + in $x + " 0 "$ is string concatenation, but the + in $n + 1$ is addition.

If we aren’t going to add any more bits, we can just use the green box, if we are going to add some more bits, we can try adding each of “0” and “1″, then asking LI for their best guess about cloud.

Diamond is almost the same as cloud, it just tells you which of the two numbers is bigger, not what that bigger number is. This is what we use to construct our really good bit string, the one that makes LI of greenbox as large as possible.

Here is how we put those bits together.

Suppose that the string we want to create is $n$ bits long.

We start with scroll 0 being the empty string. Once we get to scroll $n$ , we have our answer.

Note that we could just ask LI

“what’s the first bit of the best possible answer?”,

“what’s the second bit of the best possible answer?”, …

The reason this doesn’t work very well is suppose we mark bitstrings like this

“1”+[answer to very tricky puzzle] gets 100 points

“0”+ [anything you like] gets 99 points

“1”+[wrong answer to the puzzle] gets 0 points

The first bit to the best possible answer is “1”. However, if LI can’t answer the puzzle, then you will find better strings on average by starting with “0″.

The method shown here will output “0” if LI has an accurate idea of its own capabilities. LI should know what it can and can’t do if it has had enough time to think.