Integer Decompiler

Find the shortest program for a number

Placeholder result

High-level program: (Hover for more info)

What is this tool?

The Integer Decompiler allows you to find the shortest program that outputs a given integer. In technical terms, it computes the time-bounded Kolmogorov complexity of that integer.

Short programs are interesting as they can provide insight about numbers. Running a computation and getting 1073741825 as a result does not teach us much, but knowing that 1073741825=2³⁰+1 can hint at the structure of the solution.

The long, trivial description corresponds to a long program ("print 1073741825"), while the short description means that there's a short program outputting the same number ("print 2³⁰+1"). Having a short program generating it indicates that a number is special - that it has structure.

Example

Let's say we're studying perfect numbers (numbers that are equal to the sum of their divisors). We write some code, and manage to find the first few:

6, 28, 496, 8128, 33550336

The numbers are all even, but apart from that, no special structure is immediately apparent. Let's look at their shortest programs.

For each number, the Integer Decompiler shows the low-level program ("raw program") and a somewhat easier-to-understand translation ("high-level program"). For the first four numbers, we get "trivial" programs, that simply list the digits of the number:

Number	High-level program
6	6
28	28
496	496
8128	8128
The fifth number, however, has a more interesting program:
33550336	3 2 [ -1 12 [ ×2 ] ]

Let's see what this program does (see the language reference):

3	Pushes 3 into the stack
2	Pushes 2 into the stack
[	Pops the 2 and executes the loop body (-1 12 [ ×2 ]) two times
-1	Subtracts 1 from the number at the top of the stack
12	Pushes 12 into the stack
[	Pops the 12 and executes the inner loop (×2) 12 times
×2	Multiplies the number at the top of the stack by 2
]	End of the inner loop
]	End of the outer loop

So, the program builds 33550336 as (((3 - 1) ⋅ 2¹²) - 1) ⋅ 2¹² = ((2 ⋅ 2¹²) - 1) ⋅ 2¹² = (2¹³ - 1) ⋅ 2¹². Looking at the other numbers, they also have this form:

6 = (2² - 1) ⋅ 2¹
28 = (2³ - 1) ⋅ 2²
496 = (2⁵ - 1) ⋅ 2⁴
8128 = (2⁷ - 1) ⋅ 2⁶

This leads to an interesting conjecture: perfect numbers have the form (2ⁿ⁺¹ - 1) ⋅ 2ⁿ. In this case, the conjecture turns out to be true, and we've just discovered (part of) the Euclid-Euler theorem.

Language Reference

The language used by Integer Decompiler is a stack-based language. Program execution starts with an empty stack and all commands operate on that stack. There are no variables or other types of memory.

When the program finishes, the value at the top of the stack is considered as the program output.

Commands

The following are the base commands of the language. These are the commands executed by the interpreter and the commands that are counted to determine the length of a program.

Command	Action
0 1	Push the corresponding number into the stack
_0	Double the top number in the stack (x → 2x)¹
_1	Double the top number in the stack and add one (x → 2x+1)¹
+	Pop two numbers from the stack, and push their sum
-	Pop two numbers from the stack, and push their difference. If the result is negative, the program terminates with an error.
DROP<N>	Remove the N'th element from the stack²
TAKE<N>	Read the N'th element of the stack, without removing it, and push it to the stack²
MOVE<N>	Remove the N'th element from the stack and push it back to the top of the stack²
[ ]	Loop: When [ is reached, a number K is popped from the stack, and then the code between the brackets is executed K times.

¹ The _0 and _1 commands are only allowed after 1, _0 or _1. For example, the following program is illegal: 1 1 + _0
² Elements are numbered from the top, such that element 0 is the number at the top of the stack.

Balance rules

For a program to be legal, it has to obey two rules:

No superfluous values: When the program finishes, the stack must contain a single number. This number will be the output of the program.
Balanced loops: A loop must not change the number of elements in the stack. At the end of each loop iteration, the number of elements must be the same as when the loop started. Note, however, that the number of elements is allowed to change during the iteration, as long as it returns to its initial value when ] is reached.

High-level commands

To make it easier to understand what a program does, programs are also shown in a high-level representation. Each high-level command represents one or more base commands.

Command	Action	Equivalent base command(s) (examples)
<N>	Push the number N to the stack	1 (for 1) 1 _0 _0 _1 (for 9)
×<N>	Multiply the number at the top of the stack by N	TAKE0 + (for ×2) TAKE0 TAKE0 + + (for ×3)
+<N>	Add N to the number at the top of the stack	1 + (for +1) 1 _0 + (for +2)
DUP	Duplicate the number at the top of the stack (so it will appear twice)	TAKE0
SWAP	Swap the top two numbers in the stack	MOVE1

How It Works

When you press the "Go" button, the Integer Decompiler searches the number in its database. The database is essentially a large table of number-shortest program (SP) pairs.

Database generation

The basic algorithm to create a table of SPs is to scan all programs up to some maximum length:

Algorithm 1
sp_table = empty dictionary
For len from 1 to N:

For each program p of length len:

x = The result of running p
If x>M

continue

If x not in sp_table:

sp_table[x] = p

Algorithm 1 generates a table containing the SP for each integer x≤M if this program is up to N commands long. In practice, the running time of each program is also limited, so some long-running SPs might be missing from the table.

Algorithm 1 runs all programs having up to N commands. The Integer Decompiler language has 13 commands, so there are 13^L programs of length L. Setting L=12 gives around 10¹³ programs, or about a day at 100M programs/sec. Therefore, this basic algorithm is limited to programs of up to 12-13 commands.

Optimization

To discover longer SPs, Algorithm 1 can be improved by skipping classes of "uninteresting" programs. These are programs that definitely won't appear in sp_table because they're either invalid (finish with an error) or suboptimal (output the same number as some shorter program). The following are some examples of classes that can be skipped:

(Invalid) Programs starting with any command except 0 or 1. All others will cause an error as the first command.
(Invalid) Programs with invalid use of _0 or _1 (these can only be used after 1, _0 or _1).
(Invalid) Programs with unbalanced loop commands (e.g. ... [ ... ] ] ... ).
(Invalid) Programs that try to pop more values than there are on the stack at a certain time. Due to the balance rules of the language, it is easy to detect such programs without having to execute them.
(Suboptimal) Programs containing an empty loop ([ ]). Such loop simply pops a single value from the stack, so it is equivalent to the single command DROP0.
(Suboptimal) Programs containing a pair of commands that is a no-op: 0 +, TAKE0 DROP0

In addition, many command sequences are equivalent. For example, TAKE0 TAKE0 and TAKE0 TAKE1 both add two copies of the top element in the stack. For each group of equivalent sequences, only one has to be checked, and programs containing any of the other sequences can be ignored.

The database of the Integer Decompiler was generated with an implementation of Algorithm 1 that includes the aforementioned optimizations (and some others). The computation took around a day on a dual-core PC.

About

Being able to find the shortest program that generates a number, a sequence or a function has many interesting uses: discovering regularity in numbers, predicting sequences and inverting functions. These ideas are well known (search for "Algorithmic information theory"), yet there aren't any implementations.

The lack of implementations can be attributed to a basic fact of algorithmic information theory: in general, finding the shortest program is uncomputable (that is, impossible). However, if the running time of the program is restricted, the problem becomes computable.

The Integer Decompiler was created to investigate this time-limited variant: What do the shortest programs look like? What are their statistical properties? How hard is it to compute shortest programs of interesting size?

Language selection

The theory of Kolmogorov complexity tells us that it doesn't matter which language we use for our programs: the length of the shortest programs will only change by a constant. In practice, however, language selection does matter.

An ideal language for a tool like the Integer Decompiler will be:

Aligned with our intuitive notion of simplicity: Short programs should implement simple functions, and simple functions should be implementable as short programs.
Terse: Building the integer decompiler database requires scanning all programs up to a certain length. Having features that are not necessary for the generation of numbers, such as I/O, increases the amount of programs that have to be scanned.
Simple to understand: A main goal of the Integer Decompiler is to help humans to understand how a number might have been generated. The answer to this question is given as a program, so it should be easy to understand what the program does.

First attempt

An early version of this project used the BF language (without the input & output commands). This is a Turing-complete language with just 6 simple operations: incrementing / decrementing, moving the "memory pointer" left and right, and starting / ending a loop.

However, of the resulting programs, even some of the shorter ones turned out to be quite complex (if you know BF, try to understand how the one for 100 works). Many of them implement a chaotic process, with a few counters influencing each other, that results in the required number "by coincidence". Implementing such processes in BF requires just a few commands, while addition or multiplication of numbers require a bit more. Therefore, programs of this type usually end up being the shortest producing a given number.

Therefore, while BF fulfills requirement (2), it fails (1) and (3). The short BF programs do not implement functions that we'd consider "simple". Understanding what a program does is hard, and often requires running it in a simulator and watching how the memory contents evolve.

The current language

The Integer Decompiler language was designed to avoid the problems that BF had.

To make it simple to understand, it was built as a stack based language. With a stack based language, the shortest programs usually use few variables, as accessing values deep in the stack requires more commands. The balance rules also aid by making the stack depth constant at any given program location, and eliminating programs that leave unused values on the stack.

To align it with our expectations of simplicity, the basic concepts of constants, addition and subtraction were made built-in commands. In BF, these have to be constructed from simpler commands, penalizing their use.

Future work

The power of the Integer Decompiler is determined by the reach of its database. Raising the maximal program length or runtime will allow it to detect more advanced (and interesting) concepts. Currently, there is a lot of room for improvement in the database generation: both by adding algorithmic improvements, and by using more computation time.

At a higher level, the idea that short programs correspond to simple explanations can be used for other tasks. For example, finding the most likely function given input-output pairs, or predicting the next elements of a sequence by finding the shortest program that generates the known ones (This is sometimes called "universal sequence prediction").

MAX_LENGTH	1
MAX_OUTPUT
MAX_CELL_VALUE
MAX_RUNTIME