[ Question ]

What tools exist to compute all possible programs?

by Alexei 2mo9th Sep 20191 min read2 comments

18


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.

New Answer
Ask Related Question
New Comment
Write here. Select text for formatting options.
We support LaTeX: Cmd-4 for inline, Cmd-M for block-level (Ctrl on Windows).
You can switch between rich text and markdown in your user settings.

2 Answers

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).

http://minikanren.org/

See https://en.m.wikipedia.org/wiki/Iota_and_Jot This is a way to enumerate all possible programs as binary numbers.