It was just announced that IOI 2027 will take place in Potsdam, Germany. This makes Germany join one of the now 6 countries who have/will have hosted an IOI twice, along with Greece, Egypt, Bulgaria, Hungary and Singapore (2x online).

This is just something I've been testing around for a few hours and thought was pretty neat so I decided to share it here. Please don't take it too seriously :)

What is able to express "any program"

Fortunately Alan Turing already solved this problem for us, and defined the term "Turing complete" to qualify anything that can express any possible Turing machine (thus, being able to express any algorithm/function/computable thing). One quite famous Turing-complete programming language is Brainfuck, an esoteric programming language that has no practical use (much like this own experiment) but was made to be challenge programmers and to be as simple as possible, having the smallest compiler. It only uses 8 symbols: +, -, >, <, [, ], ., and ,. After reading a bit about this language I thought about a Veritasium video I saw not long ago about Gödel numbering, and how it could be applied to also turn any program written in Brainfuck into an integer!

From Brainfuck to a number

Gödel's encoding works by assigning a number to every symbol used, and then when at the i-th symbol $$$s_i$$$ multiply to the answer $$$p_i^{s_i}$$$, with $$$p_i$$$ being the i-th prime. And that way, using prime factorization, we can decode the number and turn it into normal Brainfuck again. The code to do that is pretty simple, the only caveat is the need to use the numbers as strings because they can get quite big. I did all of this at dawn so I didn't really want to code from scratch, and just got the boring parts from Geeks for Geeks. Here is the encoding tool in C++ if you want to check it out.

From a number to running code

The same system works here, just get the prime factors of the number and use them to form the Brainfuck code. I also added a really cool Brainfuck interpreter that I copied from here, so just by giving a number it will run the code by itself. The complete runner code is here if you want to check it out.

Final thoughts

I tested it with a more complex program written by mitxela: a complete tic-tac-toe AI on BF, that actually works! While this may not be much, I still think it's really cool that you can give a single integer as an input to a relatively simple tool and run any conceivable program, even playable AIs. The "Gödel number" for the tic-tac-toe AI is available here, but you can generate it for any BF code in a few seconds using the encoding tool provided above. Thanks for reading this blog!