Are there tools / programs out there that try to compute and run all possible programs for some simple, custom language? Like something you might do if you were to naively run AIXI.
miniKanren is a logic/relational language. It's been used to solve questions related to programs. For example, once you give miniKanren a description of the untyped λ-calculus extended with integers you can ask it "give me programs that result in 2" and it'll enumerate programs from the constant "2" to "1 + 1" to more complicated versions using λ-expressions. It can even find quines (if the described language supports it).
See https://en.m.wikipedia.org/wiki/Iota_and_Jot This is a way to enumerate all possible programs as binary numbers.